← 研踪 PaperTrailarXiv:2611.04283 · v1
Metric TSP in Sublinear Time: Breaking Two Approximation
首次提交 2026-11-03 12:12
版本更新 2026-11-03 12:12
雷达观测 2026-11-04 23:40
摘要
The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can break the 2-approximation barrier has remained a major open problem. See problem 71 on sublinear.info. This paper resolves this open problem. We show there are fixed $\varepsilon, δ> 0$ such that a $(2-δ)$-approximation of metric TSP value can be obtained with $O(n^{2-\varepsilon})$ queries. Here $n$ is the number of vertices, and the input size is $Θ(n^2)$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 12:12 · 最新观测版本
Metric TSP in Sublinear Time: Breaking Two Approximation
The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can break the 2-approximation barrier has remained a major open problem. See problem 71 on sublinear.info. This paper resolves this open problem. We show there are fixed $\varepsilon, δ> 0$ such that a $(2-δ)$-approximation of metric TSP value can be obtained with $O(n^{2-\varepsilon})$ queries. Here $n$ is the number of vertices, and the input size is $Θ(n^2)$.
查看此版本解读 →查看此版本原文 ↗