Difference between revisions of "Open Problems:71"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Updating header)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Approximation factor for Metric TSP
 
 
|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 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.
  
Consider the following setting:
+
'''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$?
  
* '''Input:''' a set $S$ of $n$ points from a metric space $(X,d)$
+
'''Notes:'''
* '''Access:''' one can query at unit cost $d(x,y)$, for any $(x,y)\in S^2$
+
* 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.
  
Czumaj and Sohler {{cite|CzumajS-08}} 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.
+
* 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.
 
 
'''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|???}}.
 

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.