Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

  • Brute Force:

  • Held–Karp algorithm:

  • Record:

  • TSP is not in NP, and is NP-Hard

Metric TSP (MTSP)

alg. Tree-MTSP Approximation.

  1. Run MST
  2. Run DFS on the MST, record pre-time
  3. Traverse the graph in the pre-time order
  • Is 2-approximation

alg. Christofids MTSP Approximation