Difference between revisions of "Open Problems:52"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (updated header)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=TSP in the streaming model
 
 
|source=dortmund12
 
|source=dortmund12
 
|who=Christian Sohler
 
|who=Christian Sohler
Line 12: Line 11:
 
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 (see [[Open_Problems:49|Problem 49]]).
 
Earth-Mover Distance over the points in the stream (see [[Open_Problems:49|Problem 49]]).

Latest revision as of 01:59, 7 March 2013

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).