A Fast and Simple $(1+ε)$-Approximation for Minimum Spanning Trees in Doubling Metrics
For researchers working on approximation algorithms for metric spaces, this paper provides a faster deterministic algorithm for MST approximation in doubling metrics, which is a fundamental problem in computational geometry and network design.
The paper presents a deterministic algorithm for computing a (1+ε)-approximation to the minimum spanning tree of an n-point metric space with doubling dimension ddim, achieving running time 2^{O(ddim)} n (log n + ε^{-1} log^4(1/ε)). This improves the previous dependence on ε from ε^{-O(ddim)} to essentially linear in ε^{-1}, and for bounded-dimensional Euclidean metrics, it improves the previous best deterministic running time by almost a factor of ε^{-1}.
The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+ε)$-approximation to the MST of an $n$-point metric space $(X, \mathbf{d})$ of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence $ε^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+ε)$-approximation to MST in time $2^{O(\mathrm{ddim})} n \bigl(\log n + ε^{-1} \log^4(1/ε)\bigr)$. For bounded doubling dimension, this improves the previous dependence on $ε$ from $ε^{-O(\mathrm{ddim})}$ to essentially linear in $ε^{-1}$. Moreover, as a special case, our result improves the previous best deterministic running time for bounded-dimensional Euclidean metrics due to Arya and Mount~[SODA'16] by almost a factor of $ε^{-1}$. We also show that, unlike in bounded-dimensional Euclidean spaces, MSTs in bounded doubling metrics can have arbitrarily large maximum degree, while every doubling metric nevertheless admits a $(1+ε)$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log(1/ε)$.