Shortest hamiltonian path for different dimension points

Question

The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.

For example if for $k=1$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $O(n\log n)$.

My question is what happens when $k$ increases - does the solution become more and more complex or is it the same for all values of $k$ larger than $1$?

Answer 1

Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity.

Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms:

1. For every fixed $k$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
2. Trevisan showed that there is no PTAS when $k = \log n$ (unless P=NP).
3. Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $k$!