Sorting the Travelling Salesman Problem (opens in new tab)

(github.com)

3 pointsenriquepablo2y ago3 comments

3 comments

An attempt at understanding the difference that makes the sorting problem (the problem solved by sorting algorithms), but not the travelling salesman problem, efficiently solvable, looking at the topologies of their solution spaces.

tgflynn2y ago

Sorting has a simple local optimum implies global optimum property. If a list is sorted than any (not necessarily sequential) sublist is sorted, and the converse. No such property applies to TSP.

I think that the best way to think about why some combinatorial problems are hard and others easy isn't to ask what makes a problem hard, but rather what makes a problem easy. Combinatorial problems seem to be hard by default. It takes some special simplifying property to make them easy.

enriquepabloOP2y ago

The idea here is not to understand why some combinatorial problems are hard and others easy, but rather to just be able to distinguish between them. So, instead of understanding why the measure functions structure the solution spaces the way they do, treating them as black boxes and examining the structure they provide to the solution space.

j / k navigate · click thread line to collapse

3 comments

enriquepabloOP2y ago

tgflynn2y ago

Sorting has a simple local optimum implies global optimum property. If a list is sorted than any (not necessarily sequential) sublist is sorted, and the converse. No such property applies to TSP.

enriquepabloOP2y ago

j / k navigate · click thread line to collapse