Improved Approximation Algorithms for the Expanding Search Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918016027983872 |
|---|---|
| author | Griesbach, Svenja M. Hommelsheim, Felix Klimm, Max Schewior, Kevin |
| author_facet | Griesbach, Svenja M. Hommelsheim, Felix Klimm, Max Schewior, Kevin |
| contents | A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a $(2\mathrm{e} + \varepsilon)$-approximation for any $\varepsilon > 0$ for the general case. On instances where the vertex weights are binary, we achieve a $2\mathrm{e}$-approximation. Finally, we develop a polynomial-time approximation scheme (PTAS) for Euclidean graphs. Previously, only an $8$-approximation was known for all these cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_03638 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Algorithms for the Expanding Search Problem Griesbach, Svenja M. Hommelsheim, Felix Klimm, Max Schewior, Kevin Data Structures and Algorithms 68W25, 68R12 A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a $(2\mathrm{e} + \varepsilon)$-approximation for any $\varepsilon > 0$ for the general case. On instances where the vertex weights are binary, we achieve a $2\mathrm{e}$-approximation. Finally, we develop a polynomial-time approximation scheme (PTAS) for Euclidean graphs. Previously, only an $8$-approximation was known for all these cases. |
| title | Improved Approximation Algorithms for the Expanding Search Problem |
| topic | Data Structures and Algorithms 68W25, 68R12 |
| url | https://arxiv.org/abs/2301.03638 |