Difference between revisions of "Open Problems:52"
(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...") |
m (updated header) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=dortmund12 | |source=dortmund12 | ||
|who=Christian Sohler | |who=Christian Sohler | ||
}} | }} | ||
| − | We have $n$ points living in $\{1,\ldots,\Delta\}^2$ | + | We have $n$ points living in $\{1,\ldots,\Delta\}^2$. |
| − | '''Question''' | + | '''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- | + | 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 ( | + | 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).
