Difference between revisions of "Open Problems:71"
(Director's cut of the question :)) |
(Updating header) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|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 | + | 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 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 | + | '''Question:''' Can one compute a $(2-\delta)$-approximation to the length of the minimum travelling salesman tour with $o(n^2)$ queries or—even better—in $o(n^2)$ time, for a positive absolute constant $\delta$? |
'''Notes:''' | '''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. | + | * 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 (''not just its weight'') 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 | + | * For the specific case of $(1,2)$-metrics (i.e., when all distances between points are either 1 or 2), there is an $\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. |
Latest revision as of 18:41, 18 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 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 the length of the minimum travelling salesman tour 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 (not just its weight) 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 an $\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.
