Approximation Algorithms for ℓ_p-Shortest Path and ℓ_p-Group Steiner Tree

2024/04/26 by Makarychev, Yury, Ovsiankin, Max, Tani, Erasmo · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2404.17669

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 ∈ ℝ^ℓ_{≥ 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.

Cited by

• Hardness of Approximation for Shortest Path with Vector Costs

Related

• An Efficient Approximation Algorithm for the Steiner Tree Problem
• The Steiner Shortest Path Tree Problem
• Bounded Degree Group Steiner Tree Problems
• O(log²k/loglogk)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
• An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree