• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
Multi-start_iterated.pdf (586.6Kb)
Type
Article accepté pour publication ou publié
Date
2021
Journal name
Applied Soft Computing
Volume
108
Pages
107437
Publication identifier
10.1016/j.asoc.2021.107437
Metadata
Show full item record
Author(s)
Nakkala, Mallikarjun Rao
Singh, 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; Matheuristic

Related items

Showing items related by title and author.

  • Thumbnail
    Swarm intelligence, exact and matheuristic approaches for minimum weight directed dominating set problem 
    Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André (2021) Article accepté pour publication ou publié
  • Thumbnail
    Two hybrid metaheuristic approaches for the covering salesman problem 
    Pandiri, Venkatesh; Singh, Alok; Rossi, André (2019) Article accepté pour publication ou publié
  • Thumbnail
    Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 
    Lacour, Renaud (2014-07) Thèse
  • Thumbnail
    Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems 
    Cornu, Marek (2017-12-18) Thèse
  • Thumbnail
    Focus distance-aware lifetime maximization of video camera-based wireless sensor networks 
    Rossi, André; Singh, Alok; Sevaux, Marc (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo