TitleApplication of CMSA to the Minimum Capacitated Dominating Set Problem
Publication TypeConference Paper
Year of Publication2019
AuthorsDavidson PPinacho, Bouamama S, Blum C
Conference NameGenetic and Evolutionary Computation Conference (GECCO 2019)
PublisherACM Press
Conference LocationPrague, Czech Republic
Pagination321-328
Abstract

This work deals with the so-called minimum capacitated dominating set (CAPMDS) problem, which is an NP-Hard combinatorial optimization problem in graphs. In this paper we describe the application of a recently introduced hybrid algorithm known as Construct, Merge, Solve \& Adapt (CMSA) to this problem. Moreover, we evaluate the performance of a standalone ILP solver. The results show that both CMSA and the ILP solver outperform current state-of-the-art algorithms from the literature. Moreover, in contrast to the ILP solver, the performance of CMSA does not degrade for the largest problem instances. The experimental evaluation is based on a benchmark dataset containing two different graph topologies and considering graphs with variable and uniform node capacities.

DOI10.1145/3321707.3321807