A GPU-accelerated local search algorithm for the Correlation Clustering problem
Department of Computer Science, Fluminense Federal University
Simposio Brasileiro de Pesquisa Operacional (SBPO), 2015
@article{levorato2015gpu,
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},
year={2015}
}
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.
August 31, 2015 by hgpu
