2026-08-01T05:36:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20254 2024-07-02T07:52:54Z ddc:004 open_access

Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree Makarychev, Yury Ovsiankin, Max Tani, Erasmo Shortest Path Asymmetric Group Steiner Tree Sum-of-Squares 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 vector cost c_e ∈ ℝ_{≥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 𝓁_p-norm of the obtained cost vector (we assume that p ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yury Makarychev and Max Ovsiankin and Erasmo Tani 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.111 urn:nbn:de:0030-drops-202542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.111 eng https://creativecommons.org/licenses/by/4.0/legalcode