Open Problems:71 - Revision history

Krzysztof Onak: Updating header

2016-01-18T18:41:24Z

Updating header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Krzysztof to Open Problems:71 without leaving a redirect

2016-01-18T18:38:17Z

Krzysztof Onak moved page Waiting:Krzysztof to Open Problems:71 without leaving a redirect

Krzysztof Onak: Small edits

2016-01-13T02:44:19Z

Small edits

Krzysztof Onak: Director's cut of the question :)

2016-01-13T02:35:44Z

Director's cut of the question :)

Ccanonne at 02:50, 12 January 2016

2016-01-12T02:50:06Z

Ccanonne at 02:49, 12 January 2016

2016-01-12T02:49:49Z

Ccanonne at 02:38, 12 January 2016

2016-01-12T02:38:18Z

Ccanonne at 02:34, 12 January 2016

2016-01-12T02:34:07Z

Krzysztof Onak: Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Krzysztof Onak }} The open problem will appear here."

2016-01-10T04:28:07Z

Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Krzysztof Onak }} The open problem will appear here."

New page

{{Header
|title=Title of the problem
|source=baltimore16
|who=Krzysztof Onak
}}
The open problem will appear here.

@@ Line 4: / Line 4: @@
 |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.
+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 this problem with $o(n^2)$ queries (or even better, in $o(n^2)$ time) for a positive absolute constant $\delta$?
+'''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 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 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.
+* 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.

@@ Line 1: / Line 1: @@
 {{Header
-|title=Approximation factor for Metric TSP
+|title=Metric TSP Cost Approximation
 |source=baltimore16
 |who=Krzysztof Onak
 }}
-Consider the following setting:
+'''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$?
-* '''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 requires $\Omega(n^2)$ queries.
-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.
+* 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.

@@ Line 10: / Line 10: @@
 * '''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.
+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|???}}.

@@ Line 10: / Line 10: @@
 * '''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}(\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.
+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|???}}.

@@ Line 10: / Line 10: @@
 * '''Access:''' one can query at unit cost $d(x,y)$, for any $(x,y)\in S^2$
-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.
+Czumaj and Sohler {{cite|CzumajS-09}} 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.
 '''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|???}}.

← Older revision	Revision as of 18:38, 18 January 2016
(No difference)