# tcs math – some mathematics of theoretical computer science

## June 24, 2010

### The Gödel Prize, TSP, and volume growth

Filed under: Math, Open question — Tags: , , , , — James Lee @ 3:57 pm

Recently, Sanjeev Arora and Joe Mitchell won the Gödel prize for their work on Euclidean TSP. They show that given $n$ points in $\mathbb R^2$, and a parameter $\varepsilon > 0$, it is possible to compute, in polynomial time, a traveling salesman tour of the input whose length is at most a factor $1+\varepsilon$ 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 $\mathbb R^k$ for every fixed $k \geq 2$. What properties of $\mathbb R^k$ are really needed to get such an algorithm?

Certainly a key property is that the volume of a ball of radius $r$ in $\mathbb R^k$ only grows like $O(r^k)$. This ensures that one can choose an $\epsilon$-net of size at most $O(1/\epsilon)^k$ in a ball of radius ${O(1)}$, 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 $(X,d)$ be a metric space, and let $\lambda(X,d)$ be the smallest number $\lambda$ such that for every $r > 0$,every ball of radius $r$ in $X$ can be covered by $\lambda$ balls of radius $r/2$. Is there a PTAS for TSP in $X$? (In other words, the running time should be bounded by a polynomial in $n =|X|$ whose degree depends only on $\lambda(X,d)$.)

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