The Gödel Prize, TSP, and volume growth

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.

About these ads