Estimating metric TSP cost below factor 2 with sublinear queries

Given an oracle for the distances between $n$ points of a metric space, the length of the shortest tour through them can be estimated within a factor $2+\varepsilon$ from about $n$ queries, by estimating the weight of a minimum spanning tree. Nobody knows how to beat the factor 2 without reading essentially all $n^2$ distances, or whether it is possible at all.

Problem

Let $(X, d)$ be a metric space on $n$ points, accessed through an oracle that returns $d(x,y)$ for a queried pair. Let $\mathrm{TSP}(X)$ be the length of a shortest tour, a cycle visiting every point once.

Question. Is there an absolute constant $\delta > 0$ and a randomized algorithm that, for every $n$-point metric, makes $o(n^2)$ distance queries and with probability at least $2/3$ outputs an estimate $\widehat T$ with

$$\mathrm{TSP}(X) \le \widehat T \le (2-\delta)\,\mathrm{TSP}(X)?$$

The stronger version asks for $o(n^2)$ running time. Only the value is needed, not a tour.

Background

The weight of a minimum spanning tree $\mathrm{MST}(X)$ satisfies $\mathrm{MST}(X) \le \mathrm{TSP}(X) \le 2\,\mathrm{MST}(X)$, and Czumaj and Sohler showed how to estimate it within $1+\varepsilon$ in $\tilde O(n)\cdot\mathrm{poly}(1/\varepsilon)$ time [1], which gives factor $2+\varepsilon$ for the tour. Classical algorithms that do better, such as Christofides', start from an actual minimum spanning tree, but finding even a constant-factor approximate spanning tree requires $\Omega(n^2)$ queries [1]. Krzysztof Onak posed the question at the 2016 Sublinear Algorithms Workshop at Johns Hopkins University, and Chen, Khanna and Tan still call it a major open problem of the query model [3].

What is known

• Graphic metrics, shortest-path distances of a connected unweighted graph: Chen, Kannan and Khanna (ICALP 2020) gave the first estimate below 2, within $2-\varepsilon_0$ for a fixed $\varepsilon_0 > 0$ in $\tilde O(n)$ time, and within $27/14$ in $\tilde O(n^{1.5})$ time [2]. Behnezhad, Roghani, Rubinstein and Saberi (ICALP 2024) improved this to $1.83$ in $\tilde O(n)$ time and $1.66$ in $n^{2-\Omega(1)}$ time [5].
• (1,2)-metrics, where every distance is 1 or 2: factor $1.625$ in $\tilde O(n^{1.5})$ time [2], then $1.5+\varepsilon$ in $\tilde O(n)$ time [5], which supersedes the $1.75$ factor mentioned on the source page. Going further in near-linear time would require better sublinear algorithms for maximum matching [5]. An unrefereed 2026 preprint gives $1.4132\ldots+\varepsilon$ in $n^{2-\Omega_\varepsilon(1)}$ time (Alipour and Nowzari) [4].
• Limits. For graphic and (1,2)-metrics, a $(1+\varepsilon_0)$-estimate for some constant $\varepsilon_0 > 0$ needs $\Omega(n^2)$ queries, and estimating these tours is tied to estimating maximum matching size [2].
• General metrics. Chen, Khanna and Tan (ICALP 2023) beat factor 2 with $\tilde O(n^{1.5})$ queries when the metric contains a spanning tree of distance-1 edges or the algorithm is given a minimum spanning tree [3]. Without such help, no $o(n^2)$-query algorithm better than 2 is known [2, 3].

What would count as progress

• An algorithm with $o(n^2)$ queries and a proof that it estimates every metric's tour within $2-\delta$. Its estimates can be compared against exact or near-optimal tour lengths on benchmark instances as a sanity check.
• A proof that every $(2-\delta)$-estimator needs $\Omega(n^2)$ queries, for instance from two distributions over metrics whose tour lengths differ by a factor near 2 but which look alike to few queries.
• A factor below 2 with $o(n^2)$ queries for a broader class of metrics than those handled in [2, 3, 5].

References

1. A. Czumaj and C. Sohler, Estimating the weight of metric minimum spanning trees in sublinear time, SIAM J. Comput. 39(3) (2009), 904–922. doi:10.1137/060672121
2. Y. Chen, S. Kannan and S. Khanna, Sublinear algorithms and lower bounds for metric TSP cost estimation, ICALP 2020. doi:10.4230/LIPIcs.ICALP.2020.30
3. Y. Chen, S. Khanna and Z. Tan, Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics, ICALP 2023. doi:10.4230/LIPIcs.ICALP.2023.37
4. S. Alipour and A. Nowzari, Sublinear-time and semi-streaming algorithms for path cover and TSP, preprint (2026). arXiv:2610.18701
5. S. Behnezhad, M. Roghani, A. Rubinstein and A. Saberi, Sublinear algorithms for TSP via path covers, ICALP 2024, LIPIcs 297, 19. doi:10.4230/LIPIcs.ICALP.2024.19

Source

Imported from Sublinear.info, Problem 71, curated by Sublinear.info editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.