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 ε, δ> 0 such that a $(2-δ)$-approximation of metric TSP value can be obtained with O(n2-ε) queries. Here n is the number of vertices, and the input size is Θ(n²).