Metric TSP in Sublinear Time: Breaking Two Approximation

Abstract

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 $\epsilon ,\delta >0$ such that a $(2-\delta )$-approximation of metric TSP value can be obtained with $O(n^{2-\epsilon })$ queries. Here $n$ is the number of vertices, and the input size is $\Theta (n^2)$.