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

arXiv: https://arxiv.org/abs/1904.03611 · HTML: https://mlsanity.com/paper/1904.03611/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2019.

## Built on by (most cited first, 1 of 1)

- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)

## Abstract (arXiv)

We give an algorithm that computes a (1+ε)-approximate Steiner forest in near-linear time n · 2^(1/ε)O(ddim2) (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^2O(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.