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

 (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},