Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
Yair Bartal, Lee-Ad J. Gottlieb · 2021
We give an algorithm that computes a (1+є)-approximate Steiner forest in near-linear time n · 2(1/є)O(ddim2) (loglogn)2, where ddim is the doubling dimension of the metric space. This improves upon the best previous result due to Chan et al. (SIAM J. Comput. 4 (2018)), who gave a runtime of about n2O(ddim) · 2(ddim/є)O(ddim) √logn. For Steiner tree our methods achieve an even better runtime n (logn)(1/є)O(ddim2).