Efficient Local Search for Maximum Weight Cliques in Large Graphs
Yi Fan, Zongjie Ma, Kaile Su, Chengqian Li, Cong Rao, Ren-Hau Liu, Longin Jan Latecki · 2017
In this paper, we develop a local search algorithm to solve the Maximum Weight Clique (MWC) problem. Firstly we design a novel scoring function to measure the benefits of a local move. Then we develop a Cycle Estimation based ReStart (CERS) strategy to resolve the cycling issue in the local search process. Experimental results show that our solver achieves state-of-the-art performances on the large sparse graphs as well as large dense graphs. Also we present a theorem which shows the necessity of the restart strategies in current state-of-the-art local search algorithms.