Abstract
In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is 4/3. Little progress towards resolving this conjecture has been made in thirty years. We conjecture that when all edge costs c ij ∈ {1,2}, the integrality gap is 10/9. We show that this conjecture is true when the optimal subtour LP solution has a certain structure. Under a weaker assumption, which is an analog of a recent conjecture by Schalekamp, Williamson and van Zuylen, we show that the integrality gap is at most 7/6. When we do not make any assumptions on the structure of the optimal subtour LP solution, we can show that inegrality gap is at most 19/15 ≈ 1.267 < 4/3; this is the first bound on the integrality gap of the subtour LP strictly less than 4/3 known for an interesting special case of the TSP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, N., Garg, N., Gupta, S.: A 4/3-approximation for TSP on cubic 3-edge-connected graphs (2011), http://arxiv.org/abs/1101.5586
Balinski, M.L.: Integer programming: Methods, uses, computation. Management Science 12, 253–313 (1965)
Berman, P., Karpinski, M.: 8/7-approximation algorithm for (1,2)-TSP. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 641–648 (2006)
Bläser, M., Shankar Ram, L.: An Improved Approximation Algorithm for TSP with Distances One and Two. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 504–515. Springer, Heidelberg (2005)
Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization 8(4), 525–539 (2011), prior version, http://www.site.uottawa.ca/~sylvia/recentpapers/halftri.pdf (accessed June 27, 2011)
Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on Cubic and Subcubic Graphs. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 65–77. Springer, Heidelberg (2011)
Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1976)
IBM ILOG CPLEX 12.1 (2009)
Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Operations Research 2, 393–410 (1954)
Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming 69, 335–349 (1995)
McKay, B.D.: Practical graph isomorphism. Congressus Numerantium 30, 45–97 (1981)
Mömke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52th Annual Symposium on Foundations of Computer Science (2011)
Mucha, M.: 13/9-approximation for graphic TSP. In: 29th International Symposium on Theoretical Aspects of Computer Science (2012)
Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52th Annual Symposium on Foundations of Computer Science (2011)
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18, 1–11 (1993)
Schalekamp, F., Williamson, D.P., van Zuylen, A.: A proof of the Boyd-Carr conjecture. In: Proceedings of the 23nd ACM-SIAM Symposium on Discrete Algorithms (2012)
Shmoys, D.B., Williamson, D.P.: Analyzing the Held-Karp TSP bound: A monotonicity property with application. Information Processing Letters 35, 281–285 (1990)
Williamson, D.P.: Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem. Master’s thesis. MIT, Cambridge, MA (June 1990), also appears as Tech. Report MIT/LCS/TR-479
Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study 13, 121–134 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qian, J., Schalekamp, F., Williamson, D.P., van Zuylen, A. (2012). On the Integrality Gap of the Subtour LP for the 1,2-TSP. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)