RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación
Artículo científico (JournalArticle)
On the complexity of the upgrading version of the maximal covering location problem
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., 15 páginas
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 TED2021-130875B-100
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2020-114594GB-C22
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 red2018-102363-T