| dc.contributor.author | Baldomero Naranjo, Marta | |
| dc.contributor.author | Kalcsics, Jörg | |
| dc.contributor.author | Rodríguez Chía, Antonio Manuel | |
| dc.contributor.other | Estadística e Investigación Operativa | es_ES |
| dc.date.accessioned | 2024-03-08T08:35:39Z | |
| dc.date.available | 2024-03-08T08:35:39Z | |
| dc.date.issued | 2024-01-17 | |
| dc.identifier.issn | 0028-304 | |
| dc.identifier.uri | http://hdl.handle.net/10498/31336 | |
| dc.description.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. | es_ES |
| dc.format | application/pdf | es_ES |
| dc.language.iso | eng | es_ES |
| dc.publisher | Wiley | es_ES |
| dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
| dc.source | Networks (2024) | es_ES |
| dc.subject | complexity | es_ES |
| dc.subject | covering problems | es_ES |
| dc.subject | location | es_ES |
| dc.subject | networks | es_ES |
| dc.subject | upgrading problems | es_ES |
| dc.title | On the complexity of the upgrading version of the maximal covering location problem | es_ES |
| dc.type | journal article | es_ES |
| dc.rights.accessRights | open access | es_ES |
| dc.description.physDesc | 15 páginas | es_ES |
| dc.identifier.doi | 10.1002/net.22207 | |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/TED2021-130875B-100/ES/PROCESOS DE IMPREGNACIÓN DE POLIMEROS Y MATRICES POROSAS MEDIANTE FLUIDOS SUPERCRÍTICOS/ | es_ES |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-114594GB-C22/ES/OPTIMIZATION ON DATA SCIENCE AND NETWORK DESIGN PROBLEMS: DATA SCIENCE MEETS OPTIMIZATION AND NETWORK MODELS/ | es_ES |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/red2018-102363-T/ES/RED ESPAÑOLA DE CANALES IONICOS/ | es_ES |
| dc.type.hasVersion | VoR | es_ES |