zbMATH — the first resource for mathematics

Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint. (English) Zbl 1044.68783
Dechter, Rina (ed.), Principles and practice of constraint programming - CP 2000. 6th international conference, Singapore, September 18–21, 2000. Proceedings. Berlin: Springer (ISBN 3-540-41053-8). Lect. Notes Comput. Sci. 1894, 306-319 (2000).
Summary: 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 [1;n]$$ for all $$i$$, the running time is linear. This also improves upon previous results.
For the entire collection see [Zbl 0947.00041].

MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
LEDA
Full Text: