← 研踪 PaperTrailarXiv:2610.23032 · v2
On the Metric Distortion of the Minimum Spanning Tree Problem
首次提交 2026-10-16 15:09
版本更新 2026-11-16 04:17
雷达观测 2026-11-17 17:12
摘要
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 . We complement this result by showing that, for every , no deterministic ordinal algorithm guarantees distortion at most 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 endpoint cut stability achieves distortion , where is the doubling dimension; this is constant for fixed , independently of . Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with , fewer than edge-comparison queries suffice to achieve distortion at most , which is near-constant even for very large inputs.
作者备注:24 pages, 9 figures, 1 table; added references and revised the related-work discussion
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 04:17 · 最新观测版本
On the Metric Distortion of the Minimum Spanning Tree Problem
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 . We complement this result by showing that, for every , no deterministic ordinal algorithm guarantees distortion at most 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 endpoint cut stability achieves distortion , where is the doubling dimension; this is constant for fixed , independently of . Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with , fewer than edge-comparison queries suffice to achieve distortion at most , which is near-constant even for very large inputs.
查看此版本解读 →查看此版本原文 ↗