Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
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_ | 1866908393841623040 |
|---|---|
| author | Kasperski, Adam Zielinski, Pawel |
| author_facet | Kasperski, Adam Zielinski, Pawel |
| contents | In this paper, the recoverable robust shortest path problem in acyclic digraphs is considered. The interval budgeted uncertainty representation is used to model the uncertain second-stage costs. The computational complexity of this problem has been open to date. In this paper, we prove that the problem is strongly NP-hard even for the case of layered acyclic digraphs. We also show that for the discrete budgeted uncertainty, the problem is not approximable unless P=NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09425 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computational complexity of the recoverable robust shortest path problem in acyclic digraphs Kasperski, Adam Zielinski, Pawel Data Structures and Algorithms Optimization and Control In this paper, the recoverable robust shortest path problem in acyclic digraphs is considered. The interval budgeted uncertainty representation is used to model the uncertain second-stage costs. The computational complexity of this problem has been open to date. In this paper, we prove that the problem is strongly NP-hard even for the case of layered acyclic digraphs. We also show that for the discrete budgeted uncertainty, the problem is not approximable unless P=NP. |
| title | Computational complexity of the recoverable robust shortest path problem in acyclic digraphs |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2410.09425 |