{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:48Z","timestamp":1774421328474,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T00:00:00Z","timestamp":1691712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UANL through its Scientific and Technological Research Support Program","award":["PAICYT CE1837-21"],"award-info":[{"award-number":["PAICYT CE1837-21"]}]},{"name":"CONACYT","award":["FC2016-2\/1948"],"award-info":[{"award-number":["FC2016-2\/1948"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            The uniform capacitated vertex\n            <jats:italic>k<\/jats:italic>\n            -center problem is an\n            <jats:italic>\ud835\udca9\ud835\udcab<\/jats:italic>\n            -hard combinatorial optimization problem that models real situations where\n            <jats:italic>k<\/jats:italic>\n            centers can only attend a maximum number of customers, and the travel time or distance from the customers to their assigned center has to be minimized. This article introduces a polynomial-time constructive heuristic algorithm that exploits the relationship between this problem and the minimum capacitated dominating set problem. The proposed heuristic is based on the one-hop farthest-first heuristic that has proven effective for the uncapacitated version of the problem. We carried out different empirical evaluations of the proposed heuristic, including an analysis of the effect of a parallel implementation of the algorithm, which significantly improved the running time for relatively large instances.\n          <\/jats:p>","DOI":"10.1145\/3604911","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T21:38:55Z","timestamp":1687469935000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["A Constructive Heuristic for the Uniform Capacitated Vertex\n            <i>k<\/i>\n            -center Problem"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7168-2799","authenticated-orcid":false,"given":"Jos\u00e9 Alejandro","family":"Cornejo-Acosta","sequence":"first","affiliation":[{"name":"Instituto Nacional de Astrof\u00edsica, \u00d3ptica y Electr\u00f3nica, Computer Science Department, Puebla Mexico and Tecnol\u00f3gico Nacional de M\u00e9xico\/ITS de Pur\u00edsima del Rinc\u00f3n, Computer Engineering Department, Guanajuato Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6334-2305","authenticated-orcid":false,"given":"Jes\u00fas","family":"Garc\u00eda-D\u00edaz","sequence":"additional","affiliation":[{"name":"Instituto Nacional de Astrof\u00edsica, \u00d3ptica y Electr\u00f3nica, Computer Science Department, Puebla, Mexico and Consejo Nacional de Humanidades, Ciencias y Tecnolog\u00edas, Mexico City, Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2656-3659","authenticated-orcid":false,"given":"Julio C\u00e9sar","family":"P\u00e9rez-Sansalvador","sequence":"additional","affiliation":[{"name":"Instituto Nacional de Astrof\u00edsica, \u00d3ptica y Electr\u00f3nica, Computer Science Department, Puebla, Mexico and Consejo Nacional de Humanidades, Ciencias y Tecnolog\u00edas, Mexico City, Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1053-5183","authenticated-orcid":false,"given":"Roger Z.","family":"R\u00edos-Mercado","sequence":"additional","affiliation":[{"name":"Universidad Aut\u00f3noma de Nuevo Le\u00f3n, Graduate Program in Systems Engineering, San Nicol\u00e1s de los Garza, NL Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0560-1687","authenticated-orcid":false,"given":"Sa\u00fal Eduardo","family":"Pomares-Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Instituto Nacional de Astrof\u00edsica, \u00d3ptica y Electr\u00f3nica, Computer Science Department, Puebla Mexico and LAAS-CNRS, Universit\u00e9 de Toulouse, France, and INSA, Toulouse France"}]}],"member":"320","published-online":{"date-parts":[[2023,8,11]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10852-004-4072-3"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.02.022"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0857-y"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1047"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1990.166"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-030-32177-2_3","volume-title":"Location Science (2nd ed.)","author":"\u00c7al\u0131k Hatice","year":"2019","unstructured":"Hatice \u00c7al\u0131k, Martine Labb\u00e9, and Hande Yaman. 2019. \\(p\\) -Center problems. In Location Science (2nd ed.), G. Laporte, S. Nickel, and F. Saldanha da Gama (Eds.). Springer, Cham, Chapter 3, 51\u201365."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.07.011"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.03.009"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2018.11.006"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.3390\/math8091551"},{"issue":"9","key":"e_1_3_1_12_2","first-page":"428","article-title":"A new approach to solving the vertex  \\(p\\) -center problem to optimality: Algorithm and computational results","volume":"45","author":"Daskin Mark S.","year":"2000","unstructured":"Mark S. Daskin. 2000. A new approach to solving the vertex \\(p\\) -center problem to optimality: Algorithm and computational results. Commun. Operat. Res. Soc. Japan 45, 9 (2000), 428\u2013436.","journal-title":"Commun. Operat. Res. Soc. Japan"},{"key":"e_1_3_1_13_2","volume-title":"Network and Discrete Location: Models, Algorithms, and Applications","author":"Daskin Mark S.","year":"2011","unstructured":"Mark S. Daskin. 2011. Network and Discrete Location: Models, Algorithms, and Applications. Wiley, New York."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90002-1"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1030.0028"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90297-O"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2933875"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9345-x"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TLA.2018.8444397"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_3_1_23_2","volume-title":"An Efficient Exact Algorithm for the Vertex  \\(p\\) -center Problem and Computational Experiments for Different Set Covering Subproblems","author":"Ilhan T.","year":"2002","unstructured":"T. Ilhan, F. Ozsoy, and M. P\u0131nar. 2002. An Efficient Exact Algorithm for the Vertex \\(p\\) -center Problem and Computational Experiments for Different Set Covering Subproblems. Technical Report. Bilkent University, Department of Industrial Engineering, Ankara, Turkey."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329776"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0889"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55537-4_60"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1012016"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.10081"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1125424.1125440"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90029-1"},{"key":"e_1_3_1_31_2","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/978-3-642-40643-0_29","volume-title":"Advances in Artificial Intelligence","author":"Quevedo-Orozco D. R.","year":"2013","unstructured":"D. R. Quevedo-Orozco and R. Z. R\u00edos-Mercado. 2013. A new heuristic for the capacitated vertex \\(p\\) -center problem. In Advances in Artificial Intelligence, C. Bielza, A. Salmer\u00f3n, A. Alonso-Betanzos, J. I. Hidalgo, L. Mart\u00ednez, A. Troncoso, E. Corchado, and J. M. Corchado (Eds.). Lecture Notes in Artificial Intelligence, Vol. 8109. Springer, Heidelberg, 279\u2013288."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.12.013"},{"issue":"2","key":"e_1_3_1_33_2","first-page":"527","article-title":"The analytical study of  \\(k\\) -center problem solving techniques","volume":"1","author":"Rana Rattan","year":"2008","unstructured":"Rattan Rana and Deepak Garg. 2008. The analytical study of \\(k\\) -center problem solving techniques. Int. J. Info. Technol. Knowl. Manage. 1, 2 (2008), 527\u2013535.","journal-title":"Int. J. Info. Technol. Knowl. Manage."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-6530-4"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.2498\/cit.2005.03.05"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20000"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/020\/07"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604911","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604911","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:05Z","timestamp":1750178765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,11]]},"references-count":37,"alternative-id":["10.1145\/3604911"],"URL":"https:\/\/doi.org\/10.1145\/3604911","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,11]]}}}