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 with non-negative costs for each edge , find a hamiltonian cycle of G with minimum cost. It is well-known that this problem is NP-Complete.

Exercise :There is no -approximation algorithm for TSP (for any ) unless P=NP.

**Metric TSP :** In Metric-TSP, the edge costs satisfy triangle inequality i.e., for all , . 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., . Approximation algorithms with factor 2 (find a minimum spanning tree (MST) of 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 , one for each edge . For a subset , denotes the edges incident to . Let denote the sum of values of of the edges with exactly one endpoint in . For more details of Held-Karp relaxation see [HK’70, HK’71]

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 :

Charikar, Goemans and Karloff [CGK’04] showed that the integrality of Held-Karp relaxation for ATSP is at least . Frieze, Galbiati and Maffioli [FGM’82] gave a simple -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 by Blaser [Blaser’02], and to Kaplan et al [KLSS’03] and to by Feige and Singh [FS’07]. So we have an approximation factor better than !!

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 to achieve an integrality gap of . Is there a
polynomial-sized(in )instanceachieving an integrality gap of ?

**References :**

**[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*.Nicos Christofides**[Christofides’76]****,****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*

** **

** **

** **

** **

** **

** **

** **

** **