@conference {1506024,
	title = {Reward-based region optimal quality guarantees},
	booktitle = {Workshop on Optimisation in Multiagent Systems (OPTMAS) at AAMAS 2011	},
	year = {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 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.},
	author = {Meritxell Vinyals and Shieh, Eric and Cerquides, Jesus and Juan Antonio Rodriguez-Aguilar and Yin, Zhengyu and Tambe, Milind and Bowring, Emma}
}
