Show simple item record

dc.contributor.authorNakkala, Mallikarjun Rao
dc.contributor.authorSingh, Alok
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRossi, André
dc.date.accessioned2021-11-09T11:48:37Z
dc.date.available2021-11-09T11:48:37Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22178
dc.language.isoenen
dc.subjectCapacitated dominating seten
dc.subjectDominating seten
dc.subjectIterated local searchen
dc.subjectInteger linear programmingen
dc.subjectMatheuristicen
dc.subject.ddc005en
dc.titleMulti-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis 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.en
dc.relation.isversionofjnlnameApplied Soft Computing
dc.relation.isversionofjnlvol108en
dc.relation.isversionofjnldate2021-09
dc.relation.isversionofjnlpages107437en
dc.relation.isversionofdoi10.1016/j.asoc.2021.107437en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-11-09T11:46:48Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record