cid e51d34c0ce18a800f22333abd981db36c0764b02085663f63425aebc0b630f21 · original · open access · via openalex
Title: MB-DPOP: a new memory-bounded algorithm for distributed optimization Authors: Adrian Petcu; Boi V. Faltings Venue: Infoscience (Ecole Polytechnique Fédérale de Lausanne) Year: 2007 Canonical: openalex:https://openalex.org/W1570298768 URL: https://openalex.org/W1570298768 Collector: openalex OA: true ABSTRACT In distributed combinatorial optimization problems, dynamic programming algorithms like DPOP ([Petcu and Faltings, 2005]) require only a linear number of messages, thus generating low communication overheads. However, DPOP’s memory requirements are exponential in the induced width of the constraint graph, which may be prohibitive for problems with large width. We present MB-DPOP, a new hybrid algorithm that can operate with bounded memory. In areas of low width, MB-DPOP operates like standard DPOP (linear number of messages). Areas of high width are explored with bounded propagations using the idea of cycle-cuts [Dechter, 2003]. We introduce novel DFS-based mechanisms for determining the cycle-cutset, and for grouping cycle-cut nodes into clusters. We use caching between clusters to reduce the complexity to exponential in the largest number of cycle cuts in a single cluster. We compare MB-DPOP with ADOPT [Modi et al., 2005], the current state of the art in distributed search with bounded memory. MB-DPOP consistently outperforms ADOPT on 3 problem domains, with respect to 3 metrics, providing speedups of up to 5 orders of magnitude. 1