Lesson 3

There are many approaches to solving the traveling salesman problem. Below we provide a very brief overview.

• Heuristic methods. These are methods that work well in practice but do not have provable guarantees.
  • Branch-and-bound method. This is probably the most popular exhaustive method in situations where an optimal solution needs to be found. The results are impressive: they can find a provably optimal solution on graphs with tens of thousands of vertices. Linear programming solvers are used to optimize the search.
    

    

  
  
  • Local search (in particular, the simulated annealing method). Used in situations where a good enough route needs to be found quickly. The idea is simple and natural: start with any cycle and try to improve it with local modifications. This finds a local (not global) optimum. It is often used in commercial logistics programs because it works fast, gives good results, and, unlike some other methods, easily adapts to additional constraints (e.g., when there are time windows during which points need to be visited).
    

    

  
  
  • Nearest neighbor algorithm. This is a simple greedy algorithm: from the current point, go to the nearest unvisited one. It works very quickly and occasionally gives acceptable results, but there are datasets where it performs quite poorly.
  
  

• Exact algorithms. The most famous one is the Bellman-Held-Karp algorithm, based on dynamic programming with a runtime of \(O(n^{2}2^{n})\) (where \(n\) is the number of vertices in the graph, as usual). A faster algorithm in general has not been found, but for undirected graphs, there is the Björklund algorithm with a runtime of \(O(1{,}7^{n})\).
• Approximation algorithms. These are algorithms that work quickly and find a solution that is guaranteed to be not much longer than the optimal one. It is known that in general, constructing such an algorithm is difficult. However, if edge weights are a metric, there is a known \(1{,}5\)-approximation algorithm. This is a relatively simple algorithm, presented in 1972 independently by Christofides and Serdyukov. For the Euclidean special case (where vertices are just points, for example, in a plane), Arora and Mitchell even constructed an approximation scheme: an algorithm that finds a \((1+\varepsilon)\)-approximation for any \(\varepsilon>0\) (and works longer the smaller \(\varepsilon\) is).

  

  For the curious 🤓

  Very recently, at the end of 2022, Karlin, Klein, and Gharan designed a \(\frac{3}{2}-\varepsilon\) approximation algorithm for metric TSP, for some \(\varepsilon>10^{-36}\). That is, they improved upon the Christofides–Serdyukov algorithm after 50 years.