On the complexity of the upgrading version of the Maximal CoveringLocation Problem

Resumen

We study the upgrading version of the maximal covering location problem with edge length modifications on networks (Up-MCLP). The UpMCLP aims at locating p facilities to maximize the coverage taking into account that the length of the edges can be reduced subject to a budget constraint. Therefore, we look for both solutions: the optimal location of p facilities and the optimal upgraded network. Note that for each edge, we are given its current length, an upper bound on the maximal reduction of its length, and a cost per unit of reduction (which can be different for each edge). Furthermore, a total budget for reductions is given. In this talk, we focus on the complexity of this problem. Since it is a particular case of the Maximal Covering Location Problem, the Up-MCLP is NP-hard on general graphs. We analyze different types of graphs (paths, trees, stars, etc.) and study the complexity of the single-facility and the multi-facility version of the problem under different assumptions on the model parameters. We prove that this problem can be solved in polynomial time and pseudo-polynomial time in some particular cases. We derive algorithms for solving them. Moreover, we show several particular casesin which the problem is NP-hard.