Reward-based region optimal quality guarantees
Meritxell Vinyals, Eric Shieh, Jesús Cerquides, Juan A. Rodríguez-Aguilar, Zhengyu Yin, Milind Tambe, Emma Bowring · 2011
Abstract. Distributed constraint optimization (DCOP) is a promising approach to coordination, scheduling and task allocation in multi agent networks. DCOP is NP- hard [6], so an important line of work focuses on developing fast incomplete solution algorithms that can provide guaran-tees on the quality of their local optimal solutions. Region optimality [11] is a promising approach along this line: it provides quality guarantees for region optimal solutions, namely solutions that are optimal in a specific region of the DCOP. Region optimality generalises k- and t-optimality [7, 4] by allowing to explore the space of criteria that define regions to look for solutions with better quality guarantees. Unfortunately, previous work in region-optimal quality guarantees fail to exploit any a-priori knowledge of the reward structure of the problem. This paper addresses this shortcoming by defining reward-dependent re-gion optimal quality guarantees that exploit two different levels of knowl-edge about rewards, namely: (i) a ratio between the least minimum re-ward to the maximum reward among relations; and (ii) the minimum and maximum rewards per relation. 1