A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs. Given an undirected graph with positive weights on the vertices, the maximum weight clique problem (MWCP) consists in finding a clique with maximum total weight. In this paper, we present a CPU-GPU local search heuristic for solving the MWCP on massive graphs. The heuristic is based on two new neighborhood structures for the problem. These neighborhoods are explored using an efficient procedure that is suitable to be mapped onto a GPU-based massively parallel architecture. We test the proposed heuristic on real-world massive graphs with millions of edges and vertices. The results indicate that, even when the heuristic is executed on a CPU-only architecture, it is able to outperform the best-known heuristics for the MWCP. Moreover, the hybrid CPU-GPU implementation obtained an average speedup of up to 12 times over the CPU-only implementation.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
- Sun, Yuan; Wang, Sheng; Shen, Yunzhuang; Li, Xiaodong; Ernst, Andreas T.; Kirley, Michael: Boosting ant colony optimization via solution prediction and machine learning (2022)
- Nogueira, Bruno; Barboza, Erick: A FPGA-based accelerated architecture for the continuous GRASP (2021)
- Nogueira, Bruno; Tavares, Eduardo; Maciel, Paulo: Iterated local search with tabu search for the weighted vertex coloring problem (2021)
- Nogueira, Bruno; Pinheiro, Rian G. S.: A GPU based local search algorithm for the unweighted and weighted maximum (s)-plex problems (2020)
- Wang, Yiyuan; Cai, Shaowei; Chen, Jiejiang; Yin, Minghao: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem (2020)
- Nogueira, Bruno; Pinheiro, Rian G. S.: A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs (2018)