Difference between revisions of "Open Problems:52"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(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...")
 
Line 4: Line 4:
 
|who=Christian Sohler
 
|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
 
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
 
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
 
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]]).

Revision as of 04:39, 12 December 2012

Suggested by Christian Sohler
Source Dortmund 2012
Short link https://sublinear.info/52

We have $n$ points living in $\{1,\ldots,\Delta\}^2$.

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 (see Problem 49).