Tight Bounds for $(1+ε)$-Approximation for Minimum Spanning Trees in Doubling Metrics
Jan Höckendorff, Felix Hommelsheim, Christian Sohler, Di Yue
原文摘要
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 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+ε)$-approximate MST in time $$ O_{\mathrm{ddim}}\left(n\log n+ \min\left\{n^2,\frac{n}ε\log(1/ε)\right\}\right) $$ in the standard real RAM model with a unit-cost exact-distance oracle. For bounded doubling dimension, this improves the previous dependence on $ε$ to essentially linear in $ε^{-1}$. We complement this algorithm with a lower bound of $$ Ω\!\left(n\log n+ \min\left\{n^2,\frac{n}ε\log(1/ε)\right\}\right) $$ on running time in the same model, already for metrics of doubling dimension at most seven, showing that our running time is essentially tight. For points in $\mathbb R^d$ with $d = O(1)$, exploiting Euclidean geometry allows us to further improve the dependence on $ε$. We obtain a $(1+ε)$-approximate MST in expected time $$ O_d\left( n \log n + \min\left\{n^2, \frac{n}{ε^{1 - β_d}} \log^{1-β_d}(1/ε) \right\} \right) $$ for some $β_d=Θ(1/d)$, improving the accuracy-dependent term $nε^{-2}\log^2(1/ε)$ of Arya and Mount [SODA'16].
cs.DS