A novel local search algorithm for the minimum capacitated dominating set

Ruizhi Li, Shuli Hu, Peng Zhao, Yupeng Zhou and Minghao Yin

Journal of the Operational Research Society, 2018, vol. 69, issue 6, 849-863

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.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1057/s41274-017-0268-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:69:y:2018:i:6:p:849-863

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1057/s41274-017-0268-6

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().