# zbMATH — the first resource for mathematics

$$O(n \log n)$$ filtering algorithms for unary resource constraint. (English) Zbl 1094.90566
Régin, Jean-Charles (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. First international conference, CPAIOR 2004, Nice, France, April 20–22, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21836-X/pbk). Lecture Notes in Computer Science 3011, 335-347 (2004).
Summary: So far, edge-finding is the only one major filtering algorithm for unary resource constraint with time complexity $$O(n\log n)$$. This paper proposes $$O(n\log n)$$ versions of another two filtering algorithms: not-first/not-last and propagation of detectable precedences. These two algorithms can be used together with the edge-finding to further improve the filtering. This paper also propose new $$O(n\log n)$$ implementation of fail detection (overload checking).
For the entire collection see [Zbl 1051.68022].

##### MSC:
 90B35 Deterministic scheduling theory in operations research 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 90C27 Combinatorial optimization
Full Text: