Faster Adaptive Set Intersections for Text Searching. Jeremy Barbay, A. López-Ortiz, Tyler Lu. Proceedings of 5th International Workshop on Experimental Algorithms (WEA), Lecture Notes in Computer Science 4007, Springer, pp. 146-157, 2006. [Postscript file]

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.