Multi-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problem
Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André (2021), Multi-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problem, Applied Soft Computing, 108, p. 107437. 10.1016/j.asoc.2021.107437
TypeArticle accepté pour publication ou publié
Journal nameApplied Soft Computing
MetadataShow full item record
Author(s)Nakkala, Mallikarjun Rao
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)This paper presents a multi-start iterated local search (MS-ILS), an exact approach based on an improved integer linear programming (ILP) model, and a matheuristic combining the ILP approach with MS-ILS through solution merging for the minimum capacitated dominating set (CAPMDS) problem for undirected graphs. This problem is an extension of the well-known minimum dominating set problem, where there is a cap on the number of nodes that each node can dominate, and the goal is to find a dominating set of minimum cardinality where the number of dominated nodes for each dominating node is within this cap. This -hard problem has several real world applications in resource constrained environments such as clustering of wireless sensor networks along with selection of cluster heads, document summarization in information retrieval. Computational results on the standard benchmark instances of this problem show the superiority of our approaches over state-of-the-art approaches available in the literature in their respective categories.
Subjects / KeywordsCapacitated dominating set; Dominating set; Iterated local search; Integer linear programming; Matheuristic
Showing items related by title and author.