Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909183647940608 |
|---|---|
| author | Makarychev, Yury Ovsiankin, Max Tani, Erasmo |
| author_facet | Makarychev, Yury Ovsiankin, Max Tani, Erasmo |
| contents | We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a non-negative vector cost $c_e \in \mathbb{R}^{\ell}_{\ge 0}$. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the $\ell_p$-norm of the obtained cost vector (we assume that $p \ge 1$ is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17669 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree Makarychev, Yury Ovsiankin, Max Tani, Erasmo Data Structures and Algorithms We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a non-negative vector cost $c_e \in \mathbb{R}^{\ell}_{\ge 0}$. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the $\ell_p$-norm of the obtained cost vector (we assume that $p \ge 1$ is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results. |
| title | Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17669 |