Título | A COP Model For Graph-Constrained Coalition Formation |
Publication Type | Journal Article |
Year of Publication | 2018 |
Authors | Bistaffa F, Farinelli A |
Journal | Journal of Artificial Intelligence Research |
Volume | 62 |
Paginación | 133-153 |
Editorial | AAAI Press |
Resumen | We consider Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation in which the set of valid coalitions is restricted by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP, and we solve such COP with a highly-parallel approach based on Bucket Elimination executed on the GPU, which is able to exploit the high constraint tightness of COP-GCCF. Results show that our approach outperforms state of the art algorithms (i.e., DyCE and IDPG) by at least one order of magnitude on realistic graphs, i.e., a crawl of the Twitter social graph, both in terms of runtime and memory. |
URL | https://www.jair.org/index.php/jair/article/view/11205 |
DOI | 10.1613/jair.1.11205 |