Open Problems:52 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:59:49Z

updated header

Krzysztof Onak at 04:44, 12 December 2012

2012-12-12T04:44:13Z

Krzysztof Onak at 04:40, 12 December 2012

2012-12-12T04:40:21Z

Krzysztof Onak at 04:39, 12 December 2012

2012-12-12T04:39:33Z

Andoni: Created page with "{{Header |title=TSP in the streaming model |source=dortmund12 |who=Christian Sohler }} We have $n$ points living in $\{1,\ldots,\Delta\}^2$ space. '''Question''': Can we appr..."

2012-12-12T01:30:51Z

Created page with "{{Header |title=TSP in the streaming model |source=dortmund12 |who=Christian Sohler }} We have $n$ points living in $\{1,\ldots,\Delta\}^2$ space. '''Question''': Can we appr..."

New page

{{Header
|title=TSP in the streaming model
|source=dortmund12
|who=Christian Sohler
}}
We have $n$ points living in $\{1,\ldots,\Delta\}^2$ space.

'''Question''': Can we approximate the value of the TSP tour (Traveling Salesman
Problem) of the $n$ points when streaming over the points in one pass, using
small space ($\log^{O(1)}\Delta$).

One can achieve a $2-$approximation by computing a minimum spanning tree
in small space, and use the MST to approximate TSP. The question is
whether one can obtain an approximation factor $c < 2$ in polylog space?

There are other natural related question, such as computing the
Earth-Mover Distance over the points in the stream (has appeared previously as [[Open_Problems:49|Problem 49]]).

@@ Line 12: / Line 12: @@
 One can achieve a $2$-approximation by computing a minimum spanning tree
 in small space, and use the MST to approximate TSP. The question is
-whether one can obtain an approximation factor $c < 2$ in polylog space?
+whether one can obtain an approximation factor $c < 2$ in polylog space.
 There are other natural related question, such as computing the
 Earth-Mover Distance over the points in the stream (see [[Open_Problems:49|Problem 49]]).

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Christian Sohler

@@ Line 4: / Line 4: @@
 |who=Christian Sohler
 }}
-We have $n$ points living in $\{1,\ldots,\Delta\}^2$ space.
+We have $n$ points living in $\{1,\ldots,\Delta\}^2$.
-'''Question''': Can we approximate the value of the TSP tour (Traveling Salesman
+'''Question:''' Can we approximate the value of the TSP tour (Traveling Salesman
 Problem) of the $n$ points when streaming over the points in one pass, using
-small space ($\log^{O(1)}\Delta$).
+small space ($\log^{O(1)}\Delta$)?
-One can achieve a $2-$approximation by computing a minimum spanning tree
+One can achieve a $2$-approximation by computing a minimum spanning tree
 in small space, and use the MST to approximate TSP. The question is
 whether one can obtain an approximation factor $c < 2$ in polylog space?
 There are other natural related question, such as computing the
-Earth-Mover Distance over the points in the stream (has appeared previously as [[Open_Problems:49|Problem 49]]).
+Earth-Mover Distance over the points in the stream (see [[Open_Problems:49|Problem 49]]).