Problem 71: Metric TSP Cost Approximation

Suggested by	Krzysztof Onak
Source	Baltimore 2016
Short link	https://sublinear.info/71

Consider the following setting:

• Input: a set $S$ of $n$ points from a metric space $(X,d)$
• Access: one can query at unit cost $d(x,y)$, for any $(x,y)\in S^2$

Czumaj and Sohler [CzumajS-09] established that, on input $\varepsilon$, one can approximate the weight of the minimum spanning tree $\operatorname{weight}(\textsf{MST}(S))$ up to a multiplicative $(1+\varepsilon)$ in time $\tilde{O}(n\operatorname{poly}(\frac{1}{\varepsilon})$. In particular, this implies that it is possible to get a $(2+\varepsilon)$-approximation of $\operatorname{weight}(\textsf{TSP}(S))$ with the same time complexity.

Question: can one beat this factor $2$ with only $o(n^2)$ queries? (And, even stronger, in $o(n^2)$ time?)

Note: this is for arbitrary metrics. Under stronger assumptions, one can do better: for instance, it is known that a factor $\frac{7}{4}$ is achievable for $(1,2)$-metrics [???].