A novel local search algorithm for the minimum capacitated dominating set

The minimum capacitated dominating set problem, an extension of the classic minimum dominating set problem, is an important NP-hard combinatorial optimization problem with a wide range of applications. The aim of this paper is to design a novel local search algorithm to solve this problem. First, the vertex penalizing strategy is introduced to define the scoring method so that our algorithm could increase the diversity of the solutions. Accordingly, a two-mode dominated vertex selecting strategy is introduced to choose the dominated vertices by the added vertex to achieve more promising solutions. After that, an intensification scheme is proposed to make full use of the capacity of each vertex and to improve the solutions effectively. Based on these strategies, a novel local search framework, as we call local search based on vertex penalizing and two-mode dominated vertex selecting strategy (LS_PD), is presented. LS_PD is evaluated against several state-of-the-art algorithms on a large collection of benchmark instances. The experimental results show that in most benchmark instances, LS_PD performs better than its competitors in terms of both solution quality and computational efficiency.