# Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree

Preprint · Yury Makarychev, Max Ovsiankin, Erasmo Tani

- Archive id: arxiv:2404.17669
- Published: 2024-04-26
- arXiv: https://arxiv.org/abs/2404.17669
- Source URL: https://arxiv.org/abs/2404.17669
- PDF: https://arxiv.org/pdf/2404.17669
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.