Hacker News Reader

Hey man, this is just a person’s fun and imaginative side project. Is there a reason you’re offering such serious and negative critical commentary on this?

View on HN

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.

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

Reply on news.ycombinator.com