Coalition Structure Generation with the Graphic Processor Unit

Krzysztof Pawlowski, Karol Kurach, Tomasz Michalak, Talal Rahwan
Institute of Informatics, University of Warsaw, Poland
University of Oxford, Tech. report CS-RR-13-07, 2013


   title={Coalition Structure Generation with the Graphic Processor Unit},

   author={Paw{l}owski, Krzysztof and Kurach, Karol and Michalak, Tomasz and Rahwan, Talal},



Download Download (PDF)   View View   Source Source   



Coalition Structure Generation-the problem of finding the optimal set of coalitions – has received considerable attention in recent AI literature. The fastest exact algorithm to solve this problem is IDP-IP*, due to Rahwan et al. (2012). This algorithm is a hybrid of two previous algorithms, namely IDP and IP. As such, it is desirable to speed up IDP as this will, in turn, improve upon the state-of-the-art. In this paper, we present IDPG-the first coalition structure generation algorithm based on the Graphics Processing Unit (GPU). This follows a promising, new algorithm design paradigm that can provide significant speed ups. We show that IDPG is faster than IDP by two orders of magnitude.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: