Difference between revisions of "Open Problems:71"
(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=Approximation factor for Metric TSP |
|source=baltimore16 | |source=baltimore16 | ||
|who=Krzysztof Onak | |who=Krzysztof Onak | ||
}} | }} | ||
| − | + | ||
| + | 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 [???].
