RT journal article
T1 On the complexity of the upgrading version of the maximal covering location problem
A1 Baldomero Naranjo, Marta
A1 Kalcsics, Jörg
A1 Rodríguez Chía, Antonio Manuel
A2 Estadística e Investigación Operativa
K1 complexity
K1 covering problems
K1 location
K1 networks
K1 upgrading problems
AB 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.
PB Wiley
SN 0028-304
YR 2024
FD 2024-01-17
LK http://hdl.handle.net/10498/31336
UL http://hdl.handle.net/10498/31336
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 11-nov-2026