ALCOMFT-TR-03-27

Irit Katriel and Sven Thiel
Fast Bound Consistency for the Global Cardinality Constraint
MPI. Work package 4. September 2003.

Abstract: We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n+n') plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n' is the number of values in the union of their ranges. We thus offer a fast alternative to Régin's arc consistency algorithm [Regin] which runs in time O(n^3/2n') and space O(n· n'). Our algorithm can also narrow the bounds for the number of occurrences of each value, which has not been done before.

Postscript file: ALCOMFT-TR-03-27.ps.gz (117 kb).