Difference between revisions of "Open Problems:71"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Krzysztof Onak }} The open problem will appear here.")
 
(Updating header)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Title of the problem
 
 
|source=baltimore16
 
|source=baltimore16
 
|who=Krzysztof Onak
 
|who=Krzysztof Onak
 
}}
 
}}
The open problem will appear here.
+
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 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 {{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.