Abstract.
A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the metric STSP (Symmetric Traveling Salesman Problem) is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the metric ATSP (Asymmetric Traveling Salesman Problem). Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of ‘‘hard-to-round’’ solutions of the relaxations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Boyd, S., Carr, R.: Finding Low Cost TSP and 2-matching Solutions Using Certain Half-Integer Subtour Vertices. Working Paper, 1999
Carr, R., Ravi, R.: A New Bound for the 2-Edge Connected Subgraph Problem. IPCO Proceedings, 1998, pp. 112–125
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Tech. Rep., GSIA, Carnegie Mellon University, 1976
Frieze, A., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12, 23–39 (1982)
Goemans, M., Bertsimas, D.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60, 145–166 (1993)
Goemans, M.: Worst Case Comparison of Valid Inequalities for the TSP. Math. Program. 69, 335–349 (1995)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, 1988
Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970)
Lovász, L.: On some connectivity properties of Eulerian graphs. Acta Mathematica Academiae Scientiarum Hungaricae 28, 129–138 (1976)
Monma, C.L., Munson, B.S., Pulleyblank, W.R.: Minimum weight two-connected spanning networks. Math. Program. 46, 153–171 (1990)
Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1), 1–11 (1993)
Sahni, S., Gonzalez, T.: P-complete approximation problems. JACM 23, 555–565 (1976)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Carr, R., Vempala, S. On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Math. Program., Ser. A 100, 569–587 (2004). https://doi.org/10.1007/s10107-004-0506-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0506-y