de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint

Mehlhorn, K., & Thiel, S. (2000). Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint. In Principles and practice of constraint programming - CP 2000 (CP-00): 6th international conference, CP 2000 (pp. 306-319). Berlin, Germany: Springer.

Item is

### Basic

show hide
Genre: Conference Paper

### Files

show Files
hide Files
:
Mehlhorn148.pdf (Publisher version), 226KB
Description:
-
Visibility:
Private
MIME-Type / Checksum:
application/pdf
-
-
-

show

### Creators

show
hide
Creators:
Mehlhorn, Kurt1, Author
Thiel, Sven1, Author
Dechter, Rina, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

### Content

show
hide
Free keywords: -
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.

### Details

show
hide
Language(s): eng - English
Dates: 2008-01-222000
Pages: -
Publishing info: -
Rev. Method: -
Identifiers: eDoc: 344445
Other: Local-ID: C1256428004B93B8-0086A54D2188D040C12569D6002EF134-MehlhornThiel2000
Degree: -

### Event

show
hide
Title: Untitled Event
Place of Event: Singapore
Start-/End Date: -

show

### Source 1

show
hide
Title: Principles and practice of constraint programming - CP 2000 (CP-00) : 6th international conference, CP 2000
Source Genre: Proceedings
Creator(s):
-
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 306 - 319 Identifier: ISBN: 3-540-41053-8

### Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
Creator(s):
-
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 1894 Sequence Number: - Start / End Page: - Identifier: -