Solving TSP: From Heuristics to a Potential Polynomial-Time Breakthrough

prat8897.github.io

3 pointssigna112 comments

According to http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.h... the optimal solution for eil51 is 426 (the linked page has a tour of 428.87) and the optimal solution for st70 is 675 (the linked page has a tour of 677.11).

What's with the 12-34-21-33 loop shown on Concorde's st70 path as shown on OP's article? You'd expect it to avoid intersecting routes in a final answer to a given problem.

Reply on news.ycombinator.com