Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Mehlhorn, Kurt
Thiel, Sven
dblp
dblp
Editor(s):
Dechter, Rina
dblp
BibTeX cite key*:
MehlhornThiel2000
Title, Booktitle
Title*:
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint
Booktitle*:
Principles and practice of constraint programming - CP 2000 (CP-00) : 6th international conference, CP 2000
Event, URLs
URL of the conference:
http://www.comp.nus.edu.sg/~cp2000
URL for downloading the paper:
http://link.springer.de/link/service/series/0558/bibs/1894/18940306.htm
Event Address*:
Singapore
Language:
English
Event Date*
(no longer used):
September, 18 - September, 21
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1894
Number:
Month:
September
Pages:
306-319
Year*:
2000
VG Wort Pages:
30
ISBN/ISSN:
3-540-41053-8
Sequence Number:
DOI:
10.1007/3-540-45349-0_23
Note, Abstract, ©
(LaTeX) Abstract:
We present narrowing algorithms for the sortedness and the alldifferent
constraint which achieve bound-consistency.
The algorithm for the sortedness constraint takes as input $2n$ intervals $X_1,
\dots, X_n$, $Y_1, \dots, Y_n$ from a linearly ordered set $D$.
Let $\mathcal{S}$ denote the set of all tuples $t \in X_1 \times \cdots \times
X_n \times Y_1 \times \cdots \times Y_n$ such that the last $n$ components of
$t$ are obtained by sorting the first $n$ components. Our algorithm determines
whether $\mathcal{S}$ is non-empty and if so reduces the intervals to
bound-consistency. The running time of the algorithm is asymptotically the
same as for sorting the interval endpoints. In problems where this is faster
than $O(n \log n)$, this improves upon previous results.
The algorithm for the alldifferent constraint takes as input $n$ integer
intervals $Z_1, \dots, Z_n$. Let $\mathcal{T}$ denote all tuples $t \in Z_1
\times \cdots \times Z_n$ where all components are pairwise different. The
algorithm checks whether $\mathcal{T}$ is non-empty and if so reduces the
ranges to bound-consistency. The running time is also asymptotically the
same as for sorting the interval endpoints. When the constraint is for example
a permutation constraint, i.e. $Z_i \subseteq \range{1}{n}$ for all $i$, the
running time is linear. This also improves upon previous results.
Keywords:
Constraint Programming, Propagation, Narrowing
HyperLinks / References / URLs:
www.mpi-sb.mpg.de/~sthiel
Download
Access Level:
Intranet
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat
BibTeX Entry:
@INPROCEEDINGS
{
MehlhornThiel2000
,
AUTHOR = {Mehlhorn, Kurt and Thiel, Sven},
EDITOR = {Dechter, Rina},
TITLE = {Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint},
BOOKTITLE = {Principles and practice of constraint programming - CP 2000 (CP-00) : 6th international conference, CP 2000},
PUBLISHER = {Springer},
YEAR = {2000},
VOLUME = {1894},
PAGES = {306--319},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Singapore},
MONTH = {September},
ISBN = {3-540-41053-8},
DOI = {10.1007/3-540-45349-0_23},
}
Entry last modified by Anja Becker, 03/02/2010
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Sven Thiel
Created
01/16/2001 09:32:44 AM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Sven Thiel
Sven Thiel
Edit Dates
22.01.2008 09:02:08
30.08.2006 16:39:57
30.08.2006 16:28:05
25/07/2001 10:25:28
04/09/2001 12:25:24 PM