A GPU-accelerated local search algorithm for the Correlation Clustering problem

Mario Levorato, Lucia Drummond, Yuri Frota, Rosa Figueiredo
Department of Computer Science, Fluminense Federal University
Simposio Brasileiro de Pesquisa Operacional (SBPO), 2015


   title={A GPU-accelerated local search algorithm for the Correlation Clustering problem},

   author={Levorato, Mario and Drummond, L{‘u}cia and Frota, Yuri and Figueiredo, Rosa},



Download Download (PDF)   View View   Source Source   



The solution of the Correlation Clustering (CC) problem can be used as a criterion to measure the amount of balance in signed social networks, where positive (friendly) and negative (antagonistic) interactions take place. Metaheuristics have been used successfully for solving not only this problem, as well as other hard combinatorial optimization problems, since they can provide sub-optimal solutions in a reasonable time. In this work, we present an alternative local search implementation based on GPGPUs, which can be used with existing GRASP and ILS metaheuristics for the CC problem. This new approach outperforms the existing local search procedure in execution time, with similar solution quality, presenting average speedups from x1.8 to x28.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: