Local Search

A more popular approach is local search: we start off with a valid tour and then use local moves to improve the tour.

Basic hill-climbing algorithm:

• Pick a tour (perhaps using the MST approximation).
• While there is some local move that improves the tour, make it.

Terminates at a ``local minimum.'' Kind of like a ``minimal'' tour in that the only way to improve it is to do something drastic.