Recently, Sanjeev Arora and Joe Mitchell won the Gödel prize for their work on Euclidean TSP. They show that given points in , and a parameter , it is possible to compute, in polynomial time, a traveling salesman tour of the input whose length is at most a factor more than the length of the optimum tour. (This is called a polynomial-time approximation scheme, or PTAS.)

Later, Arora extended this to work in for every fixed . What properties of are really needed to get such an algorithm?

Certainly a key property is that the volume of a ball of radius in only grows like . This ensures that one can choose an -net of size at most in a ball of radius , which is essential for using dynamic programming. In my opinion, this leads to the most fascinating problem left open in this area:

*Is bounded volume growth the only property needed to get a PTAS?*

This would imply that the use of Euclidean geometry in Arora’s algorithm is non-essential. We can state the question formally as follows. Let be a metric space, and let be the smallest number such that for every ,every ball of radius in can be covered by balls of radius . Is there a PTAS for TSP in ? (In other words, the running time should be bounded by a polynomial in whose degree depends only on .)

The problem is open, though there are some partial results by Talwar.

### Like this:

Like Loading...

*Related*

[...] A PTAS for TSP in doubling spaces was solved by Bartal, Gottlieb, and Krauthgamer in this STOC 2012 paper. [...]

Pingback by Open question recap | tcs math - some mathematics of theoretical computer science — February 25, 2013 @ 12:28 pm