zbMATH — the first resource for mathematics

Approximations in distributed optimization. (English) Zbl 1153.90583
van Beek, Peter (ed.), Principles and practice of constraint programming – CP 2005. 11th international conference, CP 2005, Sitges, Spain, October 1–5, 2005. Proceedings. Berlin: Springer (ISBN 978-3-540-29238-8/pbk). Lecture Notes in Computer Science 3709, 802-806 (2005).
Summary: We present a parameterized approximation scheme for distributed combinatorial optimization problems based on dynamic programming. The algorithm is a utility propagation method and requires a linear number of messages. For exact computation, the size of the largest message is exponential in the width of the constraint graph. We present a distributed approximation scheme where the size of the largest message can be adapted to the desired approximation ratio, \(\alpha \). The process is similar to a distributed version of the minibucket elimination scheme, performed on a DFS traversal of the problem.
The second part of this paper presents an anytime version of the algorithm, that is suitable for very large, distributed problems, where the propagations may take too long to complete.
Simulation results show that these algorithms are a viable approach to real world, loose optimization problems, possibly of unbounded size.
For the entire collection see [Zbl 1140.68002].

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
Full Text: DOI