Publication year: 2011
Source: Artificial Intelligence, Volume 175, Issues 16-17, October-November 2011, Pages 2061-2074
Travis Service, Julie Adams
Randomization can be employed to achieve constant factor approximations to the coalition structure generation problem in less time than all previous approximation algorithms. In particular, this manuscript presents a new randomized algorithm that can generate aapproximate solution intime, improving upon the previous algorithm that requiredtime to guarantee the same performance. Also, the presented new techniques allow aapproximate solution to be generated in the optimal time ofand improves on the previous best approximation ratio obtainable intime of. The presented algorithms are based upon a careful analysis of the sizes and numbers of coalitions in the smallest optimal coalition structures.An empirical analysis of the new randomized algorithms compared to their deterministic counterparts is provided. We find that the presented randomized algorithms generate solutions with utility comparable to what is returned by their deterministic counterparts (in some cases producing better results on average). Moreover, a significant speedup was found for most approximation ratios for the randomized algorithms over the deterministic algorithms. In particular, the randomizedapproximate algorithm runs in approximatelyof the time required for the deterministicapproximation algorithm for problems with between 20 and 27 agents.