3 ms·

I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordina

I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordinates in some plane and where the distances between two points is defined as the geometric distance. The article talks about the problem where the distances between cities are given (and not based on their coordinates). The later is a much harder problem.

mousebaiker 6y ago
The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates. Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it. [1] https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409