4 ms·

It looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown

It looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown and effort though - very useful.

MaxBarraclough 6y ago
> It's novel, but not reliable. Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets. If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.) As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle. (Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)
- FartyMcFarter 6y ago
  > It's an NP-complete problem Finding the optimal solution is NP-complete, but approximations are not necessarily so: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Complexity_of_approximation https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
  - MaxBarraclough 6y ago
    Right, I should have made that point more clear. The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems. Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.

It looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown and effort though - very useful.

MaxBarraclough 6y ago

> It's novel, but not reliable. Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets. If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.) As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle. (Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)

FartyMcFarter 6y ago
> It's an NP-complete problem Finding the optimal solution is NP-complete, but approximations are not necessarily so: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Complexity_of_approximation https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
- MaxBarraclough 6y ago
  Right, I should have made that point more clear. The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems. Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.