IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i9p1551-d411451.html
   My bibliography  Save this article

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

Author

Listed:
  • 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
    Consejo Nacional de Ciencia y Tecnología, Mexico City 03940, 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)

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.

Suggested Citation

  • José Alejandro Cornejo Acosta & Jesús García Díaz & Ricardo Menchaca-Méndez & Rolando Menchaca-Méndez, 2020. "Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(9), pages 1-16, September.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:9:p:1551-:d:411451
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/9/1551/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/9/1551/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Albareda-Sambola, Maria & Díaz, Juan A. & Fernández, Elena, 2010. "Lagrangean duals and exact solution to the capacitated p-center problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 71-81, February.
    2. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    3. Fuyu Yuan & Chenxi Li & Xin Gao & Minghao Yin & Yiyuan Wang, 2019. "A Novel Hybrid Algorithm for Minimum Total Dominating Set Problem," Mathematics, MDPI, vol. 7(3), pages 1-11, February.
    4. Ruizhi Li & Shuli Hu & Peng Zhao & Yupeng Zhou & Minghao Yin, 2018. "A novel local search algorithm for the minimum capacitated dominating set," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(6), pages 849-863, June.
    5. Dorit S. Hochbaum & David B. Shmoys, 1985. "A Best Possible Heuristic for the k -Center Problem," Mathematics of Operations Research, INFORMS, vol. 10(2), pages 180-184, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hinojosa, Yolanda & Marín, Alfredo & Puerto, Justo, 2023. "Dynamically second-preferred p-center problem," European Journal of Operational Research, Elsevier, vol. 307(1), pages 33-47.
    2. Jesús García-Díaz & Lil María Xibai Rodríguez-Henríquez & Julio César Pérez-Sansalvador & Saúl Eduardo Pomares-Hernández, 2022. "Graph Burning: Mathematical Formulations and Optimal Solutions," Mathematics, MDPI, vol. 10(15), pages 1-20, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Raphael Kramer & Manuel Iori & Thibaut Vidal, 2020. "Mathematical Models and Search Algorithms for the Capacitated p -Center Problem," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 444-460, April.
    2. Hinojosa, Yolanda & Marín, Alfredo & Puerto, Justo, 2023. "Dynamically second-preferred p-center problem," European Journal of Operational Research, Elsevier, vol. 307(1), pages 33-47.
    3. Pedro Pinacho-Davidson & Christian Blum, 2020. "Barrakuda : A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(11), pages 1-26, October.
    4. Nicolas Dupin & Frank Nielsen & El-Ghazali Talbi, 2021. "Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front," Mathematics, MDPI, vol. 9(4), pages 1-30, February.
    5. Espejo, Inmaculada & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2015. "Capacitated p-center problem with failure foresight," European Journal of Operational Research, Elsevier, vol. 247(1), pages 229-244.
    6. Alexander Estes & David J. Lovell & Michael O. Ball, 2019. "Unsupervised prototype reduction for data exploration and an application to air traffic management initiatives," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 467-510, December.
    7. Yi Xu & Jigen Peng & Yinfeng Xu, 2018. "The mixed center location problem," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1128-1144, November.
    8. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    9. Barbara Anthony & Vineet Goyal & Anupam Gupta & Viswanath Nagarajan, 2010. "A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 79-101, February.
    10. Zhuqi Miao & Balabhaskar Balasundaram & Eduardo L. Pasiliao, 2014. "An exact algorithm for the maximum probabilistic clique problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 105-120, July.
    11. Renbo Huang & Guirong Zhuo & Lu Xiong & Shouyi Lu & Wei Tian, 2023. "A Review of Deep Learning-Based Vehicle Motion Prediction for Autonomous Driving," Sustainability, MDPI, vol. 15(20), pages 1-43, October.
    12. Wei Ding & Ke Qiu, 2020. "Approximating the asymmetric p-center problem in parameterized complete digraphs," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 21-35, July.
    13. Jesus Garcia-Diaz & Jairo Sanchez-Hernandez & Ricardo Menchaca-Mendez & Rolando Menchaca-Mendez, 2017. "When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem," Journal of Heuristics, Springer, vol. 23(5), pages 349-366, October.
    14. Sergio Cabello, 2023. "Faster distance-based representative skyline and k-center along pareto front in the plane," Journal of Global Optimization, Springer, vol. 86(2), pages 441-466, June.
    15. Abdul Suleman, 2017. "On ill-conceived initialization in archetypal analysis," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 11(4), pages 785-808, December.
    16. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    17. Lingping Kong & Jeng-Shyang Pan & Václav Snášel & Pei-Wei Tsai & Tien-Wen Sung, 2018. "An energy-aware routing protocol for wireless sensor network based on genetic algorithm," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 67(3), pages 451-463, March.
    18. Lihe Guan & Hong Wang, 2022. "A heuristic approximation algorithm of minimum dominating set based on rough set theory," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 752-769, August.
    19. Yi Xu & Jigen Peng & Wencheng Wang & Binhai Zhu, 2018. "The connected disk covering problem," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 538-554, February.
    20. Contreras, Ivan & Fernández, Elena & Reinelt, Gerhard, 2012. "Minimizing the maximum travel time in a combined model of facility location and network design," Omega, Elsevier, vol. 40(6), pages 847-860.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:9:p:1551-:d:411451. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.