@article{74ab8aa344874ef7ac8947194c97c0cf,
title = "On the complexity of the upgrading version of the Maximal Covering Location Problem",
abstract = "In this article, we study the complexity of the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem is NP-hard on general networks. However, in some particular cases, we prove that this problem is solvable in polynomial time. The cases of star and path networks combined with different assumptions for the model parameters are analysed. In particular, we obtain that the problem on star networks is solvable in (Formula presented.) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in (Formula presented.) time, while the (Formula presented.) -facility problem is NP-hard even with uniform costs and upper bounds (maximal upgrading per edge), as well as, integer parameter values. Furthermore, a pseudo-polynomial algorithm is developed for the single facility problem on trees with integer parameters.",
keywords = "Location, covering problems, networks, upgrading problems, complexity",
author = "Marta Baldomero-Naranjo and Jӧrg Kalcsics and Rodriguez-Chia, {Antonio M.}",
note = "Funding Information: All authors were partially supported by research project PID2020‐114594GB‐C22 (Agencia Estatal de Investigaci{\'o}n, Spain and the European Regional Development's funds (ERDF)) and research project RED2022‐134149‐T (Spanish Ministry of Science and Innovation). Marta Baldomero‐Naranjo was partially supported by MCIN/AEI/10.13039/501100011033 and the European Union “NextGenerationEU”/PRTR through project TED2021‐130875B‐I00 and the BritishSpanish Society Scholarship Programme 2018 (Telef{\'o}nica and the BritishSpanish Society). J{\"o}rg Kalcsics was partially supported by Grant number EST2019‐047 for research stays in Universidad de C{\'a}diz (Plan Propio de Investigaci{\'o}n y Transferencia de la UCA). Antonio M. Rodr{\'i}guez‐Ch{\'i}a was partially supported by MCIN/AEI/10.13039/501100011033 and the European Union “NextGenerationEU”/PRTR through project TED2021‐130875B‐I00. Publisher Copyright: {\textcopyright} 2024 The Authors. Networks published by Wiley Periodicals LLC.",
year = "2024",
month = jan,
day = "17",
doi = "On the complexity of the upgrading version of the maximal covering location problem",
language = "English",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
}