Abstract
A long-standing conjecture in Combinatorial Optimization is that the integrality gap of the Held-Karp LP relaxation for the Asymmetric Traveling Salesman Problem (ATSP) is a constant. In this paper, we give a simpler LP relaxation for the ASTP. The integrality gaps of this relaxation and of the Held-Karp relaxation are within a constant factor of each other. Our LP is simpler in the sense that its extreme solutions have at most 2n − 2 non-zero variables, improving the bound 3n − 2 proved by Vempala and Yannakakis for the extreme solutions of the Held-Karp LP relaxation. Moreover, more than half of these non-zero variables can be rounded to integers while the total cost only increases by a constant factor.
We also show that given a partially rounded solution, in an extreme solution of the corresponding LP relaxation, at least one positive variable is greater or equal to 1/2.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, N., Khandekar, R., Nagarajan, V.: Additive Guarantees for Degree Bounded Directed Network Design. In: STOC 2008 (2008)
Bläser, M.: A new Approximation Algorithm for the Asymmetric TSP with Triangle Inequality. In: SODA 2002, pp. 638–645 (2002)
Charikar, M., Goemans, M.X., Karloff, H.J.: On the Integrality Ratio for Asymmetric TSP. In: FOCS 2004, pp. 101–107 (2004)
Carr, R., Vempala, S.: On the Held-Karp relaxation for the asymmetric and symmetric TSPs. Mathematical Programming 100(3), 569–587 (2004)
Frank, A.: Personal communication
Frieze, A., Galbiati, G., Maffioli, M.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12 (1982)
Goemans, M.X.: Minimum Bounded Degree Spanning Trees. In: FOCS 2006, pp. 273–282 (2006)
Gutin, G., Punnen, A.P. (eds.): Traveling Salesman Problem and Its Variations. Springer, Berlin (2002)
Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Operation Research 18, 1138–1162 (1970)
Hoffman, A.J.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Proc. Symp. in Applied Mathematics, Amer. Math. Soc., pp. 113–127 (1960)
Jain, K.: A factor 2 approximation for the generalized Steiner network problem. Combinatorica 21, 39–60 (2001)
Kaplan, H., Lewenstein, M., Shafir, N., Sviridenko, M.: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs. In: Proc. of IEEE FOCS, pp. 56–67 (2003)
Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Berlin (2003)
Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. In: STOC 2007, pp. 651–660 (2007)
Lau, L.C., Singh, M.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007, pp. 661–670 (2007)
Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons Ltd., Chichester (1985)
Vempala, S., Yannakakis, M.: A Convex Relaxation for the Asymmetric TSP. In: SODA 1999, pp. 975–976 (1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, T. (2008). A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)