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

Abstract

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

References in corpus (1)

• Fast Construction of Nets in Low Dimensional Metrics, and Their Applications