TitleQuality guarantees for region optimal DCOP algorithms
Publication TypeConference Paper
Year of Publication2011
AuthorsVinyals M, Shieh E, Cerquides J, Rodríguez-Aguilar JA, Yin Z, Tambe M, Bowring E
Conference NameTenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
Keywordsapproximate algorithm, bound, DCOP, region optimality

k- and t-optimality algorithms [9, 6] provide solutions to DCOPs that are optimal in regions characterized by its size and distance respectively. Moreover, they provide quality guarantees on their solutions. Here we generalise the k- and t-optimal framework to introduce C-optimality, a exible framework that provides reward-independent quality guar- antees for optima in regions characterised by any arbitrary criterion. Therefore, C-optimality allows us to explore the space of criteria (beyond size and distance) looking for those that lead to better solution qualities. We benet from this larger space of criteria to propose a new criterion, the so- called size-bounded-distance criterion, which outperforms k- and t-optimality.