Problem 52: TSP in the Streaming Model

From Open Problems in Sublinear Algorithms
Revision as of 01:30, 12 December 2012 by Andoni (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Suggested by Christian Sohler
Source Dortmund 2012
Short link https://sublinear.info/52

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