Editing Open Problems:71
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
{{Header | {{Header | ||
+ | |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-09}} established that, on input $\varepsilon$, one can approximate the weight of the minimum spanning tree $\operatorname{weight}(\text{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}(\text{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|???}}. |