
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
View/ Open
Type
Article accepté pour publication ou publiéDate
2021Journal name
Applied Soft ComputingVolume
108Pages
107437
Publication identifier
Metadata
Show full item recordAuthor(s)
Nakkala, Mallikarjun RaoSingh, Alok
Rossi, André
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 / Keywords
Capacitated dominating set; Dominating set; Iterated local search; Integer linear programming; MatheuristicRelated items
Showing items related by title and author.
-
Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André (2021) Article accepté pour publication ou publié
-
Pandiri, Venkatesh; Singh, Alok; Rossi, André (2019) Article accepté pour publication ou publié
-
Cornu, Marek (2017-12-18) Thèse
-
Rossi, André; Singh, Alok; Sevaux, Marc (2019) Article accepté pour publication ou publié