Faster Adaptive Set Intersections for Text Searching
[.ps]
[.pdf]
Abstract
We present a new propagator achieving bound consistency for the
interdistance
constraint. This constraint ensures that, among a set of variables
X_1, …, X_n, the difference between two variables is at least
p. This restriction models, in
particular, scheduling problems in which tasks require
p contiguous units of a resource to be completed.
Until now, the best known propagator for
bound consistency had time complexity
O(n^3). In this work we propose a
quadratic propagator for the same level of consistency. We then show that this
theoretical gain gives savings of an order of magnitude in our benchmark of
scheduling problems.
Bibtex Entry
