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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s