The Salesman’s Improved Paths through Forests

Abstract

We give a new, strongly polynomial-time algorithm and improved analysis for the metric s-t path Traveling Salesman Problem (TSP). It finds a tour of cost less than 1.53 times the optimum of the subtour elimination linear program (LP), while known examples show that 1.5 is a lower bound for the integrality gap.

A key new idea is the deletion of some edges of the spanning trees used in the best-of-many Christofides-Serdyukov-algorithm, which is then accompanied by novel arguments of the analysis: edge-deletion disconnects the trees, and the arising forests are then partly reconnected by “parity correction.” We show that the arising “connectivity correction” can be achieved for a minor extra cost.

On the one hand, this algorithm and analysis extend previous tools such as the best-of-many Christofides-Serdyukov-algorithm. On the other hand, powerful new tools are solicited, such as a flow problem for analyzing the reconnection cost, and the construction of a set of more and more restrictive spanning trees, each of which can still be found by the greedy algorithm. We show that these trees, which are easy to compute, can replace the spanning trees of the best-of-many Christofides-Serdyukov-algorithm.

These new methods lead to improving the integrality ratio and approximation guarantee below 1.53, as was shown in the preliminary, shortened version of this article that appeared in FOCS 2016. The algorithm and analysis have been significantly simplified in the current article, while details and explanations have been added.

References

1. Hyung-Chan An, Robert D. Kleinberg, and David B. Shmoys. 2015. Improving Christofides’ algorithm for the s-t path TSP. J. ACM 62, 5 (2015), 34:1--34:28. Preliminary version in STOC’12.
2. Nicos Christofides. 1976. Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem. Report 388. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.
3. William J. Cook. 2011. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press.
4. William H. Cunningham. 1986. On Bounds for the Metric TSP. Unpublished manuscript.
5. G. Dantzig, R. Fulkerson, and S. Johnson. 1954. Solution of a large-scale traveling-salesman problem. Operations Research 2 (1954), 393--410.
6. Jack Edmonds and Ellis L. Johnson. 1973. Matching, Euler tours and the Chinese postman. Math. Program. 5, 1 (1973), 88--124.
7. András Frank and Éva Tardos. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 1 (1987), 49--65.
8. Zhihan Gao. 2013. An LP-based 3/2-approximation algorithm for the s-t path graph traveling salesman problem. Oper. Res. Lett. 41, 6 (2013), 615--617.
9. Zhihan Gao. 2015. On the metric s-t path traveling salesman problem. SIAM J. Discrete Math. 29, 3 (2015), 1133--1149.
10. M. R. Garey, D. S. Johnson, and R. Endre Tarjan. 1976. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 4 (1976), 704--714.
11. Corinna Gottschalk and Jens Vygen. 2018. Better s-t-tours by Gao trees. Math. Program. 172, 1--2 (2018), 191--207. Preliminary version in IPCO’16.
12. M. Grötschel, L. Lovász, and A. Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 2 (1981), 169--197.
13. J. A. Hoogeveen. 1991. Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters 10, 5 (1991), 291--295.
14. D. S. Johnson and C. H. Papadimitriou. 1985. Performance guarantees for heuristics. In The Traveling Salesman Problem. Wiley, Chichester, 145--180.
15. Tobias Mömke and Ola Svensson. 2016. Removing and adding edges for the traveling salesman problem. J. ACM 63, 1 (2016), 2:1--2:28. Preliminary version in FOCS’11.
16. Frans Schalekamp, András Sebő, Vera Traub, and Anke van Zuylen. 2018. Layers and matroids for the traveling salesman’s paths. Oper. Res. Lett. 46, 1 (2018), 60--63.
17. Alexander Schrijver. 2003. Combinatorial Optimization—Polyhedra and Efficiency. Springer.
18. András Sebö. 2013. Eight-fifth approximation for the path TSP. In Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization IPCO 2013, Valparaíso, Chile, March 18--20, 2013 (Lecture Notes in Computer Science), Vol. 7801. Springer, 362--374.
19. András Sebö and Anke van Zuylen. 2016. The salesman’s improved paths: A 3/2+1/34 approximation. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9--11 October 2016, Hyatt Regency, New Brunswick, New Jersey. IEEE Computer Society, 118--127.
20. András Sebő and Jens Vygen. 2014. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34, 5 (2014), 597--629.
21. A. Serdyukov. 1978. On some extremal walks in graphs. Upravlyaemye Sistemy 17 (1978), 76--79.
22. David B. Shmoys and David P. Williamson. 1990. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inf. Process. Lett. 35, 6 (1990), 281--285.
23. Vera Traub and Jens Vygen. 2018. Approaching for the s-t-path TSP. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, January 7--10, 2018. SIAM, 1854--1864.
24. Vera Traub and Jens Vygen. 2018. Beating the integrality ratio for s-t-tours in graphs. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7--9, 2018. IEEE Computer Society, 766--777.
25. Vera Traub and Jens Vygen. 2019. An improved upper bound on the integrality ratio for the s-t-path TSP. Oper. Res. Lett. 47, 3 (2019), 225--228.
26. Jens Vygen. 2016. Reassembling trees for the traveling salesman. SIAM J. Discrete Math. 30, 2 (2016), 875--894.
27. L. A. Wolsey. 1980. Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study 13 (1980), 121--134.
28. Rico Zenklusen. 2019. A 1.5-approximation for path TSP. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, January 6--9, 2019. SIAM, 1539--1549.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

    • Graph theory

      • Approximation algorithms

      • Matchings and factors

      • Matroids and greedoids

      • Paths and connectivity problems