Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2403.20000 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913073647845376 |
|---|---|
| author | Jackiewicz, Marcel Kasperski, Adam Zieliński, Paweł |
| author_facet | Jackiewicz, Marcel Kasperski, Adam Zieliński, Paweł |
| contents | In this paper the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi_2^p-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_20000 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse Jackiewicz, Marcel Kasperski, Adam Zieliński, Paweł Computational Complexity In this paper the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi_2^p-hard. |
| title | Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2403.20000 |