Asymptotic approximation algorithms for TSP

38 Views Asked by At

I have been reading a lot about TSP approximation algorithms recently, and I noticed that most of the algorithms tend to fall under two general categories: some that have a guaranteed approximation ratio for all possible graphs (most notably the Christofides algorithm), and some that perform very well in practice but don't have any worst-case guarantees (like the Concorde TSP solver). I'm curious if there also exist algorithms that converge asymptotically on the optimal path for large values of $n$ - in other words, an algorithm for which as $n\rightarrow\infty$, the expected value of the approximation ratio converges on $1$ (when averaged over a suitable random sample of graphs, such as a set of $n$ points randomly selected in Cartesian space). Can anyone point me to such an algorithm, or provide a compelling reason why it may not exist?