On the integrality gap of the subtour LP for the 1,2-TSP
详细信息 查看全文
- 作者：Jiawei Qian ; Frans Schalekamp ; David P. Williamson…
- 关键词：Traveling salesman problem ; Subtour elimination ; Linear programming ; Integrality gap ; 90C05 ; 90C27 ; 05C70
- 刊名：Mathematical Programming
- 出版年：2015
- 出版时间：April 2015
- 年：2015
- 卷：150
- 期：1
- 页码：131-151
- 全文大小：302 KB
- 参考文献：1. Aggarwal, N., Garg, N., Gupta, S.: A 4/3-approximation for TSP on cubic 3-edge-connected graphs. CoRR abs/1101.5586 (2011)
2. Balinski, ML (1965) Integer programming: methods, uses, computation. Manag. Sci. 12: pp. 253-313 CrossRef
3. 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-48 (2006)
4. Bl?ser, M., Shankar Ram, L.: An improved approximation algorithm for TSP with distances one and two. In: Liskiewicz, M., Reischuk, R. (eds.) Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lecture Notes in Computer Science, vol. 3623, pp. 504-15. Springer (2005)
5. Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8, 525-39 (2011). Prior version available at http://www.site.uottawa.ca/sylvia/recentpapers/halftri.pdf. Accessed 27 June 2011
6. Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144(1-), 227-45 (2014). A preliminary version appeared in IPCO 2011
7. 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)
8. Dantzig, G, Fulkerson, R, Johnson, S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2: pp. 393-410
9. Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33(5), 467-74 (2005)
10. Goemans, MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Program. 69: pp. 335-349
11. Goemans, MX, Bertsimas, DJ (1990) Survivable networks, linear programming relaxations, and the parsimonious property. Math. Program. 60: pp. 145-166 CrossRef
12. IBM ILOG CPLEX 12.1 (2009)
13. McKay, BD (1981) Practical graph isomorphism. Congr. Numerantium 30: pp. 45-97
14. Mnich, M., M?mke, T.: Improved integrality gap upper bounds for TSP with distances one and two. CoRR abs/1312.2502 (2013)
15. M?mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 560-69 (2011)
16. Mucha, M.: \(\frac{13}{9}\) -approximation for graphic TSP. Theory Comput. Syst., 1-8 (2012). A preliminary version appeared in STACS 2012
17. Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 550-59 (2011)
18. Papadimitriou, CH, Yannakakis, M (1993) The traveling salesman problem with distances one and two. Math. Oper. Res. 18: pp. 1-11 CrossRef
19. Qian, J., Schalekamp, F., Williamson, D.P., van Zuylen, A.: On the integrality gap of the subtour LP for the 1,2-TSP. In: LATIN 2012: Theoretical Informatics, 10th Latin American Symposium, Lecture Notes in Computer Science, vol. 7256, pp. 606-17 (2012)
20. Schalekamp, F., Williamson, D.P., van Zuylen, A.: 2-matchings, the traveling salesman problem, and the subtour LP: A proof of the Boyd-Carr conjecture. Math. Oper. Res. 39(2), 403-17 (2014). A preliminary version appeared in SODA 2012
21. Seb?, A., Vygen, J.: Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. CoRR abs/1201.1870 (2012)
22. Shmoys, DB, Williamson, DP (1990) Analyzing the Held–Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35: pp. 281-285 CrossRef
23. Williamson, D.P.: Analysis of the Held–Karp heuristic for the traveling salesman problem. Master’s thesis, MIT, Cambridge, MA (1990). Also appears as Tech Report MIT/LCS/TR-479
24. Wolsey, LA (1980) Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13: pp. 121-134- 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Calculus of Variations and Optimal Control
Mathematics of Computing
Numerical Analysis
Combinatorics
Mathematical and Computational Physics
Mathematical Methods in Physics- 出版者：Springer Berlin / Heidelberg
- ISSN：1436-4646
文摘
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 30?years. We conjecture that when all edge costs \(c_{ij}\in \{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 et al., 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 integrality gap is at most 5/4; 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. We show computationally that the integrality gap is at most 10/9 for all instances with at most 12 cities.