Recoverable robust shortest path problem under interval budgeted uncertainty representations
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_ | 1866917721279561728 |
|---|---|
| author | Jackiewicz, Marcel Kasperski, Adam Zielinski, Pawel |
| author_facet | Jackiewicz, Marcel Kasperski, Adam Zielinski, Pawel |
| contents | In this paper, the recoverable robust shortest path problem under interval uncertainty representations is discussed. This problem is known to be strongly NP-hard and also hard to approximate in general digraphs. In this paper, the class of acyclic digraphs is considered. It is shown that for the traditional interval uncertainty, the problem can be solved in polynomial time for all natural, known from the literature, neighborhoods. Efficient algorithms for various classes of acyclic digraphs are constructed. Some negative results for general digraphs are strengthened. Finally, some exact and approximate methods of solving the problem under budgeted interval uncertainty are proposed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_05715 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recoverable robust shortest path problem under interval budgeted uncertainty representations Jackiewicz, Marcel Kasperski, Adam Zielinski, Pawel Data Structures and Algorithms In this paper, the recoverable robust shortest path problem under interval uncertainty representations is discussed. This problem is known to be strongly NP-hard and also hard to approximate in general digraphs. In this paper, the class of acyclic digraphs is considered. It is shown that for the traditional interval uncertainty, the problem can be solved in polynomial time for all natural, known from the literature, neighborhoods. Efficient algorithms for various classes of acyclic digraphs are constructed. Some negative results for general digraphs are strengthened. Finally, some exact and approximate methods of solving the problem under budgeted interval uncertainty are proposed. |
| title | Recoverable robust shortest path problem under interval budgeted uncertainty representations |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.05715 |