Distributed Multiplicative Weights Methods for DCOP
Abstract
We introduce a new framework for solving distributed constraint optimization problems that extend the domain of each variable into a simplex.We propose two methods for searching the extended domain for good assignments.The first one relaxes the problem using linear programming, finds the optimum LP solution, and rounds it to an assignment.The second one plays a cost-minimization game, finds a certain kind of equilibrium, and rounds it to an assignment.Both methods are realized by performing the multiplicative weights method in a distributed manner.We experimentally demonstrate that our methods have good scalability,and in particular, the second method outperforms existing algorithms in terms of solution quality and efficiency.
Cite
Text
Hatano and Yoshida. "Distributed Multiplicative Weights Methods for DCOP." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9425Markdown
[Hatano and Yoshida. "Distributed Multiplicative Weights Methods for DCOP." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/hatano2015aaai-distributed/) doi:10.1609/AAAI.V29I1.9425BibTeX
@inproceedings{hatano2015aaai-distributed,
title = {{Distributed Multiplicative Weights Methods for DCOP}},
author = {Hatano, Daisuke and Yoshida, Yuichi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {2074-2080},
doi = {10.1609/AAAI.V29I1.9425},
url = {https://mlanthology.org/aaai/2015/hatano2015aaai-distributed/}
}