Difference between revisions of "Open Problems:52"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m
m (updated header)
 
Line 1: Line 1:
 
{{Header
 
{{Header
|title=TSP in the Streaming Model
 
 
|source=dortmund12
 
|source=dortmund12
 
|who=Christian Sohler
 
|who=Christian Sohler

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