Held Karp Relaxation

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 $G(V,E)$ with non-negative costs $c_e$ for each edge $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 $\alpha$ -approximation algorithm for TSP (for any $\alpha \geq 1$ ) unless P=NP.

Metric TSP : In Metric-TSP, the edge costs satisfy triangle inequality i.e., for all $u,v,w \in V$ , $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., $c(u,v) = c(v,u)$ . Approximation algorithms with factor 2 (find a minimum spanning tree (MST) of $G$ and use shortcuts to obtain a tour) and factor 3/2 (find an MST, find a perfect matching on the odd degree nodes of the MST to get a eulerian graph and obtain a tour) are well-known. The factor 3/2 algorithm, known as Christofides Algorithm [Christofides’76], is the best known approximation factor for STSP. No improvement in the last three decades !!

Following is the Held-Karp Relaxation for STSP with the cut constraints and the degree constraints. The variables are $x_e$ , one for each edge $e \in E$ . For a subset $S \subset V$ , $\delta(S)$ denotes the edges incident to $S$ . Let $x(\delta(S))$ denote the sum of values of $x_e$ of the edges with exactly one endpoint in $S$ . For more details of Held-Karp relaxation see [HK’70, HK’71]

hk-stsp

Exercise : In the following instance of STSP the cost between vertices u and v is the length of the shortest path between u and v. The three long paths are of length k. Prove that this instance achieves an integrality ratio arbitrarily close to 4/3 (as k is increased).

Asymmetric TSP (ATSP) : In ATSP, the edge costs are not necessarily symmetric i.e., the underlying graph is directed. The Held-Karp relaxation for ATSP is as follows :

hk-atsp

Charikar, Goemans and Karloff [CGK’04] showed that the integrality of Held-Karp relaxation for ATSP is at least $2-\epsilon$ . Frieze, Galbiati and Maffioli [FGM’82] gave a simple $O({\log}_2{n})$ -approximation algorithm for ATSP in 1982, where n is the number of vertices. In the last eight years, this was improved to a guarantee of 0.999 ${\log}_2{n}$ by Blaser [Blaser’02], and to $\frac{4}{3}{\log}_3{n}$ Kaplan et al [KLSS’03] and to $\frac{2}{3}{\log}_2{n}$ by Feige and Singh [FS’07]. So we have an approximation factor better than ${\ln}n$ !!

Open Problems :

The long-standing open problem is to determine the exact integrality gap of Held-Karp relaxation. Many researchers conjecture that the integrality gap of Held-Karp relaxation for STSP is 4/3 and for ATSP it is bounded by a constant. The best known upper bounds are 3/2 and O(logn) respectively.

The size of the integrality gap instance of ATSP (constructed by [CGK’04]) is exponential in $1/\epsilon$ to achieve an integrality gap of $2-\epsilon$ . Is there a polynomial-sized (in $1/\epsilon$ ) instance achieving an integrality gap of $2-\epsilon$ ?

References :

Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[HK’70] Micheal Held and Richard M. Karp, The Traveling Salesman Problem and Minimum Spanning Trees, Operations Research 18, 1970, 1138–1162.
[HK’71] Michael Held and Richard Karp, The Traveling-Salesman Problem and Minimum Spanning Trees: Part II, Mathematical Programming 1, 1971, 6–25.
[Christofides’76] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
[FGM’82] A. M. Frieze, G. Galbiati and M. Maffioli, On the Worst-Case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem, Networks 12, 1982, 23–39.
[Blaser’02] M. Blaser, A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, 638–645.
[KLSS’03] H. Kaplan, M. Lewenstein, N. Shafir and M. Sviridenko, Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, 56–67.
[CGK’04] Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107
[FS’07] Uriel Feige, Mohit Singh: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. APPROX-RANDOM 2007: 104-118

3 thoughts on “Held Karp Relaxation”

Lei | October 17, 2014 at 2:46 PM

Many literature state that Held-Karp Relaxation of TSP can be solved in polynomial time, for example, by the ellipsoid method. But I always doubt whether it is feasible to obtain an HK result in polynomial time in reality. Because there are exponential number of constraints, is it easy to enumerate all subsets? Or, maybe this formulation can be solved in polynomial time, but cannot be written down in polynomial time?

- Sam | November 3, 2014 at 11:39 AM
  
  Ellipsoid runs in polynomial time as long as you have a poly-time separation oracle (which may not need to go through all exponential number of constraints)
  
Mustafa Qamar-ud-Din | October 27, 2016 at 4:04 AM

Reblogged this on Qamar-ud-Din.