3 ms·
Current best heuristics, Lin-Kernighan-Helsgaun arrive probabilistically at better percentages for TSP. Definitely makes you wonder if P = NP is even relevant
by knuthsat 6y ago
Current 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).