|
TITLE: The Inter-Distance constraint
PRESENTER: Claude-Guy Quimper, http://www.cs.uwaterloo.ca/~cquimper/, cquimper@math.uwaterloo.ca
AFFILIATION:University of Waterloo, Canada, http://www.cs.uwaterloo.ca/
DATE: Friday 28th April 2006
TIME: 11:00:00
PLACE: CSE Seminar Room, Level 1, K17
ABSTRACT:
I will give an introduction to the disjunctive scheduling problem where
tasks have equal processing times, potentially distinct release times
and deadlines, and share a same resource. I will present the algorithm
by [Garey et al. 1981] that solves the problem in O(n log n) steps.
In presence of side constraints, the problem can become NP-Hard.
Constraint programming is a powerful technique to handle such problems.
The Inter-Distance constraint ensures that, among a set of variables
{X1, ..., Xn}, the difference between two variables is at least p.
I will show how the inter-distance constraint can model a disjunctive
scheduling problem. Until now, the best known propagator achieving bound
consistency on the Inter-Distance constraint had time complexity O(n3).
I will present a quadratic propagator for the same level of consistency.
This joint work with Alejandro López-Ortiz and Gilles Pesant will be
presented at AAAI 06 in July.
BIOGRAPHY OF SPEAKER:
Claude-Guy is in the final year of his PhD at the University of Waterloo
under the supervision of Alejandro López-Ortiz, working in the area of
algorithm design in constraint programming and video-on-demand
broadcasting systems. He has published in the International Conference
on Principles and Practice of Constraint Programming (CP), the
International Joint Conference on Artificial Intelligence (IJCAI), the
National Conference on Artificial Intelligence (AAAI), the Canadian
Conference on Computational Geometry (CCCG), the European Symposium on
Algorithms (ESA), and the Annual Multimedia Computing and Networking
Conferences (MMCN).
Claude-Guy visited KRR for two months early in 2005 and during his visit
to NICTA, he collaborated with Toby Walsh and Emmanuel Hebrard to
research and develop publications in the Constraints Programming area.
Host:
Toby Walsh
Seminar Convenor:
Van Hai Ho
|
