arXiv preprint ·
On the Metric Distortion of the Minimum Spanning Tree Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices induced by these weights. We first show, through a simple example, that without assumptions on the weights, no ordinal algorithm guarantees a finite approximation ratio. We therefore focus on general metrics and present a Borůvka-inspired algorithm using only ordinal comparisons that achieves distortion $O(\log n)$. We complement this result by showing that, for every $\varepsilon>0$, no deterministic ordinal algorithm guarantees distortion at most $3/2-\varepsilon$ on all finite metric instances. We then investigate more informative settings in pursuit of constant distortion, first considering two well-studied metric classes. For tree metrics realized on the given vertex set, a more careful variant of our initial algorithm achieves distortion~$1$, recovering an optimal MST from ordinal information alone. For the broad class of doubling metrics, a different algorithm based on \emph{endpoint cut stability} achieves distortion $2^{O(D)}$, where $D$ is the doubling dimension; this is constant for fixed $D$, independently of $n$. Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with $n\geq2$, fewer than $n$ edge-comparison queries suffice to achieve distortion at most $2\log_2^* n-1$, which is near-constant even for very large inputs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Competitive Online Clustering with Movement Cost
Near-Linear Time Maximum Clique in Circular Arc Graphs
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Online geometric matching and segments block points
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.