跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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)O(\log n). We complement this result by showing that, for every ε>0\varepsilon>0, no deterministic ordinal algorithm guarantees distortion at most 3/2−ε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 endpoint cut stability achieves distortion 2O(D)2^{O(D)}, where DD is the doubling dimension; this is constant for fixed DD, independently of nn. Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with n≥2n\geq2, fewer than nn edge-comparison queries suffice to achieve distortion at most 2log⁡2∗n−12\log_2^* n-1, which is near-constant even for very large inputs.

作者备注:24 pages, 9 figures, 1 table; added references and revised the related-work discussion

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 O(log⁡n)O(\log n). We complement this result by showing that, for every ε>0\varepsilon>0, no deterministic ordinal algorithm guarantees distortion at most 3/2−ε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 endpoint cut stability achieves distortion 2O(D)2^{O(D)}, where DD is the doubling dimension; this is constant for fixed DD, independently of nn. Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with n≥2n\geq2, fewer than nn edge-comparison queries suffice to achieve distortion at most 2log⁡2∗n−12\log_2^* n-1, which is near-constant even for very large inputs.

查看此版本解读 →查看此版本原文 ↗