Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

2019/04/07 by Lee-Ad Gottlieb, Yair Bartal, Gottlieb, Lee-Ad +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1904.03611

openalex publication_date 2019/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an algorithm that computes a (1+ε)-approximate Steiner forest in near-linear time n ⋅ 2^(1/ε)^O(ddim2) (log log n)². This is a dramatic improvement upon the best previous result due to Chan et al., who gave a runtime of n^2^O(ddim) ⋅ 2^(ddim/ε)^O(ddim) √(log n). For Steiner tree our methods achieve an even better runtime n (log n)^(1/ε)^O(ddim2) in doubling spaces. For Euclidean space the runtime can be reduced to 2^(1/ε)^O(d2) n log n, improving upon the result of Arora in fixed dimension d.

Cited by

• Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

Related

• An efficient polynomial-time approximation scheme for Steiner forest in planar graphs
• A polynomial-time approximation scheme for Euclidean Steiner forest
• 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
• A PTAS for the Steiner Forest Problem in Doubling Metrics
• Strong Steiner Tree Approximations in Practice