Pseudo-tree-based Algorithm for Approximate Distributed Constraint Optimization with Quality Bounds

Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.

Authors

• Tenda Okimoto
• YongJoon Joe
• Atsushi Iwasaki The University of Electro-Communications
• Makoto Yokoo Kyushu University

Keywords

• Distributed Constraint Optimization Problem
• Pseudo-tree
• Induced Width