Approximating minimum spanning trees despite corrupted distances
Approximating Minimum Spanning Trees in Metrics under Semi-Random Corruptions
Data Structures and Algorithms
Summary
Finding the cheapest way to connect points (a minimum spanning tree) can be tricky if distances between points might be wrong or altered. The authors study what happens when some distances get corrupted randomly, and they develop algorithms that still find roughly good connections despite these errors. They investigate different cases—when errors only make distances bigger, only smaller, or both—and provide different guarantees on how close their solutions can get to the true best. Their work answers open questions about how well we can do in these challenging situations.
What this means in practice
- •For network engineers: Design reliable network topologies even when some measured distances or latencies are corrupted or fluctuate unpredictably.
- •For distributed systems developers: Construct communication trees that approximately minimize total cost despite uncertain or partially corrupted link data.
A theory result. No direct application yet.
Authors
Aditya Anand, Anupam Gupta, Rajesh Jayaram, Euiwoong Lee, Ali Vakilian
Abstract
We study the problem of finding minimum spanning trees in semi-random corrupted metrics. In this problem proposed by Bateni, Dharangutte, Jayaram, and Wang (COLT'24), we start with a metric space $\mathcal{M} = (X, d)$. The adversary independently corrupts each pairwise distance with probability $p$. The algorithm only observes these possibly corrupted distances and must output a spanning tree whose expected cost (in the true metric) is multiplicatively close to the minimum spanning tree cost. Prior work showed that losing a factor of $Ω(\log n)$ is necessary, even if the algorithm may adaptively select $O(n/\log n)$ points and probe the true distances between them. However, no upper bounds were known. We study three regimes based on whether the adversary can only increase, decrease, or arbitrarily change the corrupted distances. We show the following: (1) In the increase-only setting, we give a polynomial-time $O(1)$-approximation algorithm for any constant $0 \le p < 1$. (2) In the decrease-only setting, we give an $O(\log n)$-approximation algorithm for any constant $0 \le p < 1$. Additionally, we show an $O(\log^4 n)$-approximation algorithm that runs in quasi-polynomial time $n^{O(\log n)}$, for any constant $p \leq 0.1$. Moreover, we show that a polynomial-time algorithm computing an $n^{1/3-\varepsilon}$-approximation is unlikely to exist. (3) In the general setting, where the adversary can both increase and decrease distances, we show an $O(\log n)$-approximation algorithm for every $0 \leq p < \frac{1}{4}$. Further, we show that no $o(n)$-approximation is possible for $\frac{1}{2} \leq p < 1$. Our algorithms answer the main open question in Bateni et al.'s work; moreover, the $O(\log n)$-approximations in the latter two settings are information-theoretically optimal.