The Traveling Salesman Problem (TSP) is undoubtedly the most important and well-studied problem in Combinatorial Optimization. Today’s post is a quick overview of the Held-Karp Relaxation of TSP.

**TSP :** Given a complete undirected graph $latex G(V,E)$ with non-negative costs $latex c_e$ for each edge $latex e in E$, find a hamiltonian cycle of G with minimum cost. It is well-known that this problem is NP-Complete.

Exercise :There is no $latex alpha$-approximation algorithm for TSP (for any $latex alpha geq 1$) unless P=NP.

**Metric TSP :** In Metric-TSP, the edge costs satisfy triangle inequality i.e., for all $latex u,v,w in V$, $latex c(u,w) leq c(u,v) + c(v,w)$. Metric-TSP is also NP-complete. Henceforth, we shall focus on metric TSP.

**Symmetric TSP (STSP) :** In STSP, the edge costs are symmetric i.e., $latex c(u,v) = c(v,u)$. Approximation algorithms with factor 2 (find a minimum spanning tree (MST) of $latex G$ and…

View original post 604 more words