Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for 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