3 ms·
"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100." Complexity: O(n^2)
by djoldman 6y ago
"We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100."
Complexity: O(n^2)
- greesil 6y agoAccording to the website below, the DP solution is O(n^2 * 2^n). That would be a big speedup. https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ https://www.geeksforgeeks.org/travelling-salesman-problem-se...
- mpoteat 6y agoIf true, what implications does this have for P = NP? My intuition for a long time has been that P = NP only in the limit of an "infinitely sophisticated" algorithm. Such that as we do more research (or I suppose train larger models), we get closer and closer to the polynomial ideal.
- visarga 6y agoDoesn't apply here because this algorithm is an approximate TSP.
- deleted 6y ago[deleted]
- knuthsat 6y agoCurrent best heuristics, Lin-Kernighan-Helsgaun arrive probabilistically at better percentages for TSP. Definitely makes you wonder if P = NP is even relevant when all the interesting instances can be solved to optimality or very near to it extremely often.
- UncleMeat 6y agoSome NP-complete problems have provably bad approximations if P!=NP. You don't get the same polynomial reduction behavior if you are using approximation algorithms. So for some problems we may have utterly practical algorithms and for others we never will (assuming P!=NP).