@conference {1506989,
	title = {Local Optimal Solutions for DCOP: New Criteria, Bound, and Algorithm },
	booktitle = {AAMAS 2009 Workshop on Optimisation in Multi-Agent Systems (OptMas)},
	year = {2009},
	abstract = {Distributed constraint optimization (DCOP) is a popular formalism for modeling cooperative multi-agent systems. In large-scale
networks, finding a global optimum using complete algorithms is
often impractical, which leads to the study on incomplete algorithms. Traditionally incomplete algorithms can only find locally
optimal solution with no quality guarantees. Recent work on ksize-optimality has established bounds on solution quality, but size
is not the only criteria for forming local optimization groups. In
addition, there is only one algorithm for computing solutions for
arbitrary k and it is quite inefficient. We introduce t-distanceoptimality, which offers an alternative way to specify optimization
groups. We establish bounds for this criteria that are often tighter
than those for k-optimality. We then introduce an asynchronous local search algorithm for t-distance-optimality. We implement and
evaluate the algorithm for both t and k optimality that offer significant improvements over KOPT {\textendash} the only existing algorithm for ksize-optimality. Our experiment shows t-distance-optimality converges more quickly and to better solutions than k-size-optimality
in scale-free graphs, but k-size-optimality has advantages for random graphs.},
	author = {Yin, Zhengyu and Kiekintveld, Christopher and Kumar, Atul and Tambe, Milind}
}
