Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
<|reference_start|>Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree: 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.<|reference_end|>
@article{makarychev2024approximation,
    title={Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group
  Steiner Tree},
    author={Yury Makarychev, Max Ovsiankin, Erasmo Tani},
    journal={arXiv preprint arXiv:2404.17669},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.17669},
    primaryClass={cs.DS}
}