Difference between revisions of "Open Problems:71"
| Line 10: | Line 10: | ||
* '''Access:''' one can query at unit cost $d(x,y)$, for any $(x,y)\in S^2$ | * '''Access:''' one can query at unit cost $d(x,y)$, for any $(x,y)\in S^2$ | ||
| − | Czumaj and Sohler {{cite|CzumajS- | + | Czumaj and Sohler {{cite|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?) | '''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|???}}. | '''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:38, 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-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 [???].
