Difference between revisions of "Open Problems:71"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Krzysztof Onak }} The open problem will appear here.")
 
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Title of the problem
+
|title=Approximation factor for Metric TSP
 
|source=baltimore16
 
|source=baltimore16
 
|who=Krzysztof Onak
 
|who=Krzysztof Onak
 
}}
 
}}
The open problem will appear here.
+
 
 +
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 {{cite|CzumajS-08}} 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 {{cite|???}}.

Revision as of 02:34, 12 January 2016

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-08] 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 [???].