Difference between revisions of "Open Problems:71"
(Director's cut of the question :)) |
|||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |title= | + | |title=Metric TSP Cost Approximation |
|source=baltimore16 | |source=baltimore16 | ||
|who=Krzysztof Onak | |who=Krzysztof Onak | ||
}} | }} | ||
| + | This problem appeared in the paper of Czumaj and Sohler {{cite|CzumajS-09}}, who gave an efficient algorithm for approximating the weight of the minimum spanning tree of a metric space in the following setting. The input is a metric space $\mathcal M$ on $n$ points. For any pair $u$ and $v$ of points in $\mathcal M$, the algorithm is allowed to query their distance. The algorithm of Czumaj and Sohler computes a multiplicative $(1+\epsilon)$-approximation to the weight of the minimum spanning tree in time $\tilde O(n)\cdot\operatorname{poly}(1/\epsilon)$. This immediately yields a $(2+\epsilon)$-approximation to the length of the minimum travelling salesman tour. | ||
| − | + | '''Question:''' Can one compute a $(2-\delta)$-approximation to this problem with $o(n^2)$ queries (or even better, in $o(n^2)$ time) for a positive absolute constant $\delta$? | |
| − | + | '''Notes:''' | |
| − | + | * It is difficult to apply the approach known from the Christofides algorithm, which computes a $3/2$-approximation in the more standard setting. It requires computing a minimum spanning tree, while Czumaj and Sohler show that obtaining a constant-factor approximation to the minimum spanning tree requires $\Omega(n^2)$ queries. | |
| − | + | * For the specific case of $(1,2)$-metrics (i.e., when all distances between points are either 1 or 2), there is a $\tilde O(n)\cdot\operatorname{poly}(1/\epsilon)$-time $(1.75+\epsilon)$-approximation algorithm. It uses the fact that if there is a short travelling salesman tour, then there must be a large matching in the graph obtained by connecting pairs of points at distance 1. Therefore, the cases of long and short shortest tours can be distinguished efficiently using a known graph matching algorithm {{cite|OnakRRR-12}}. (This is a joint observation with Anupam Gupta.) However, this approach does not seem to generalize to arbitrary metrics. | |
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 02:35, 13 January 2016
| Suggested by | Krzysztof Onak |
|---|---|
| Source | Baltimore 2016 |
| Short link | https://sublinear.info/71 |
This problem appeared in the paper of Czumaj and Sohler [CzumajS-09], who gave an efficient algorithm for approximating the weight of the minimum spanning tree of a metric space in the following setting. The input is a metric space $\mathcal M$ on $n$ points. For any pair $u$ and $v$ of points in $\mathcal M$, the algorithm is allowed to query their distance. The algorithm of Czumaj and Sohler computes a multiplicative $(1+\epsilon)$-approximation to the weight of the minimum spanning tree in time $\tilde O(n)\cdot\operatorname{poly}(1/\epsilon)$. This immediately yields a $(2+\epsilon)$-approximation to the length of the minimum travelling salesman tour.
Question: Can one compute a $(2-\delta)$-approximation to this problem with $o(n^2)$ queries (or even better, in $o(n^2)$ time) for a positive absolute constant $\delta$?
Notes:
- It is difficult to apply the approach known from the Christofides algorithm, which computes a $3/2$-approximation in the more standard setting. It requires computing a minimum spanning tree, while Czumaj and Sohler show that obtaining a constant-factor approximation to the minimum spanning tree requires $\Omega(n^2)$ queries.
- For the specific case of $(1,2)$-metrics (i.e., when all distances between points are either 1 or 2), there is a $\tilde O(n)\cdot\operatorname{poly}(1/\epsilon)$-time $(1.75+\epsilon)$-approximation algorithm. It uses the fact that if there is a short travelling salesman tour, then there must be a large matching in the graph obtained by connecting pairs of points at distance 1. Therefore, the cases of long and short shortest tours can be distinguished efficiently using a known graph matching algorithm [OnakRRR-12]. (This is a joint observation with Anupam Gupta.) However, this approach does not seem to generalize to arbitrary metrics.
