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].

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: DOI