A novel local search algorithm for the minimum capacitated dominating set

Abstract

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.

Keywords:

• Local search
• vertex penalizing
• capacitated dominating set
• intensification scheme

Acknowledgements

This work was supported in part by NSFC under Grant Nos. (61370156, 61403076, 61403077, 61402070 and 61503074), the Program for New Century Excellent Talents in University (NCET-13-0724), Youth Foundation of Northeast Normal University (1309021), and Educational scientific planning of Jilin Province (1205098).