On the complexity of the upgrading version of the maximal covering location problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912033656537088 |
|---|---|
| author | Baldomero-Naranjo, Marta Kalcsics, Jörg Rodríguez-Chía, Antonio M. |
| author_facet | Baldomero-Naranjo, Marta Kalcsics, Jörg Rodríguez-Chía, Antonio M. |
| contents | 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 O(nlogn) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in O(n^3) time, while the p-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11900 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the complexity of the upgrading version of the maximal covering location problem Baldomero-Naranjo, Marta Kalcsics, Jörg Rodríguez-Chía, Antonio M. Data Structures and Algorithms Optimization and Control 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 O(nlogn) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in O(n^3) time, while the p-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. |
| title | On the complexity of the upgrading version of the maximal covering location problem |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2409.11900 |