Uncategorized

# Held Karp Relaxation My Brain is Open

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