Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
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_ | 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 |