A novel local search algorithm for the minimum capacitated dominating set
针对最小容量支配集这一NP难问题，提出一种结合顶点惩罚和双模式支配顶点选择策略的局部搜索算法，在多数基准实例上优于现有算法。
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.