Problem 71: Metric TSP Cost Approximation

From Open Problems in Sublinear Algorithms
Revision as of 02:38, 12 January 2016 by Ccanonne (talk | contribs)
Jump to: navigation, search
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 [???].