Coalition Structure Generation with the Graphic Processor Unit - Pawłowski, K; Kurach, K; Michalak, T; Rahwan, T (DCS, 2013)
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.