%0 Conference Paper %B Workshop on Optimisation in Multiagent Systems (OPTMAS) at AAMAS 2011 %D 2011 %T Reward-based region optimal quality guarantees %A Meritxell Vinyals %A Shieh, Eric %A Cerquides, Jesus %A Juan Antonio Rodriguez-Aguilar %A Yin, Zhengyu %A Tambe, Milind %A Bowring, Emma %X 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 guarantees 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 region optimal quality guarantees that exploit two different levels of knowledge about rewards, namely: (i) a ratio between the least minimum reward to the maximum reward among relations; and (ii) the minimum and maximum rewards per relation. %B Workshop on Optimisation in Multiagent Systems (OPTMAS) at AAMAS 2011 %G eng