Approximation Algorithm for TSP (Metric TSP — 2-Approximation)

For general TSP (arbitrary distances) no polytime approximation exists unless $P=NP$ (Hamiltonian cycle reduces). For Metric TSP (complete graph satisfying triangle inequality $c(u,w) ≤ c(u,v)+c(v,w)$) a constant-factor approximation exists.

2-Approximation via MST ( MST-doubling )

Approx-TSP(G, c):
  T = MST(G)  // via Prim/Kruskal $O(E\log V)$
  Perform preorder walk of T (DFS) starting at arbitrary root, list vertices in order of first visit
  Return Hamiltonian cycle visiting in that order + return to start (shortcutting repeated vertices using triangle inequality)

Analysis: Let OPT = optimal TSP tour cost. Removing one edge from OPT gives spanning tree → $c(T) ≤ c(OPT)$. Full walk of T traverses each edge twice → $c(W)=2c(T) ≤2c(OPT)$. Shortcutting via triangle inequality can only decrease cost → $c(H) ≤c(W) ≤2c(OPT)$ → 2-approximation. Time $O(V^2)$ or $O(E\log V)$.

Christofides 1.5-Approximation (better)

1. Find MST $T$.
2. Find minimum weight perfect matching $M$ on vertices of $T$ with odd degree (even number, via Blossom $O(V^3)$).
3. Combine $T∪M$ (Eulerian multigraph, all vertices even degree).
4. Find Euler tour, shortcut to Hamiltonian cycle.
   Ratio: $c(T)≤OPT$, $c(M)≤OPT/2$ → $c(H)≤1.5 OPT$.

Heuristic without guarantee: Nearest Neighbor, 2-opt local search.