Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1446-1450.
Abstract
A distributed constraint optimization problem (DCOP) is a formalism that captures the rewards and costs of local interactions within a team of agents. Because complete algorithms to solve DCOPs are unsuitable for some dynamic or anytime domains, researchers have explored incomplete DCOP algorithms that result in locally optimal solutions. One type of categorization of such algorithms, and the solutions they produce, is k-optimality; a k-optimal solution is one that cannot be improved by any deviation by k or fewer agents. This paper presents the first known guarantees on solution quality for k-optimal solutions. The guarantees are independent of the costs and rewards in the DCOP, and once computed can be used for any DCOP of a given constraint graph structure.
@inproceedings{ijcai2007p233,
title = {Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems},
author = {Pearce, Jonathan P. and Tambe, Milind},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {1446--1450},
year = {2007},
url = {https://ijcai.org/proceedings/2007/233},
}
TY - CPAPER TI - Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems AU - Pearce, Jonathan P. AU - Tambe, Milind T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 1446 EP - 1450 UR - https://ijcai.org/proceedings/2007/233 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
