Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem

José Alejandro Cornejo Acosta, Jesús García Díaz, Ricardo Menchaca-Méndez and Rolando Menchaca-Méndez
Additional contact information
José Alejandro Cornejo Acosta: Instituto Nacional de Astrofísica, Óptica y Electrónica, Santa María Tonantzintla, Puebla 72840, Mexico
Jesús García Díaz: Instituto Nacional de Astrofísica, Óptica y Electrónica, Santa María Tonantzintla, Puebla 72840, Mexico
Ricardo Menchaca-Méndez: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Rolando Menchaca-Méndez: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico

Mathematics, 2020, vol. 8, issue 9, 1-16

Abstract: The capacitated vertex k-center problem receives as input a complete weighted graph and a set of capacity constraints. Its goal is to find a set of k centers and an assignment of vertices that does not violate the capacity constraints. Furthermore, the distance from the farthest vertex to its assigned center has to be minimized. The capacitated vertex k-center problem models real situations where a maximum number of clients must be assigned to centers and the travel time or distance from the clients to their assigned center has to be minimized. These centers might be hospitals, schools, police stations, among many others. The goal of this paper is to explicitly state how the capacitated vertex k-center problem and the minimum capacitated dominating set problem are related. We present an exact algorithm that consists of solving a series of integer programming formulations equivalent to the minimum capacitated dominating set problem over the bottleneck input graph. Lastly, we present an empirical evaluation of the proposed algorithm using off-the-shelf optimization software.

Keywords: facility location; graph theory; integer programming; optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/9/1551/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/9/1551/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:9:p:1551-:d:411451

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().