Better s–t-tours by Gao trees

1. An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofides’ algorithm for the \(s\)–\(t\) path TSP. J. ACM 62, 34 (2015)

   Article  MathSciNet  Google Scholar 

2. Asadpour, A., Goemans, M.X., Mądry, A., Oveis Gharan, S., Saberi, A. : An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379–389 (2010)

3. Cheriyan, J., Friggstad, Z., Gao, Z.: Approximating minimum-cost connected \(T\)-joins. Algorithmica 72, 126–147 (2015)

   Article  MathSciNet  Google Scholar 

4. Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976)

5. Cunningham, W.H.: Testing membership in matroid polyhedra. J. Comb. Theory B 36, 161–188 (1984)

   Article  MathSciNet  Google Scholar 

6. Edmonds, J.: The Chinese postman’s problem. Bull. Op. Res. Soc. Am. 13, B-73 (1965)

7. Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88–124 (1973)

   Article  MathSciNet  Google Scholar 

8. Gao, Z.: An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s\)–\(t\) path graph traveling salesman problem. Oper. Res. Lett. 41, 615–617 (2013)

   Article  MathSciNet  Google Scholar 

9. Gao, Z.: On the metric \(s\)-\(t\) path traveling salesman problem. SIAM J. Discret. Math. 29, 1133–1149 (2015)

   Article  MathSciNet  Google Scholar 

10. Genova, K., Williamson, D.P.: An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem. In: Bansal, N., Finocchi, I. (eds.) Algorithms–ESA 2015; LNCS 9294, pp. 570–581. Springer, Berlin (2015)

    Chapter  Google Scholar 

11. Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 273–282 (2006)

12. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)

    Article  MathSciNet  Google Scholar 

13. Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970)

    Article  MathSciNet  Google Scholar 

14. Hoogeveen, J.A.: Analysis of Christofides’ heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10, 291–295 (1991)

    Article  MathSciNet  Google Scholar 

15. 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 (FOCS), pp. 550–559 (2011)

16. Schalekamp, F., Sebő, A., Traub, V., van Zuylen, A.: Layers and matroids for the traveling salesman’s paths. arXiv:1703.07170

17. Sebő, A.: Eight fifth approximation for TSP paths. In: Correa, J., Goemans, M.X. (eds.) Proceedings of the 16th IPCO Conference; LNCS 7801, Integer Programming and Combinatorial Optimization, pp. 362–374. Springer (2013)

18. Sebő, A., Vygen, J.: Shorter tours by nicer ears: 7/5-approximation for graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34, 597–629 (2014)

    Article  MathSciNet  Google Scholar 

19. Sebő, A., van Zuylen, A.: The salesman’s improved paths: 3/2 + 1/34 integrality gap and approximation ratio. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 118–127

20. Traub, V., Vygen, J.: Approaching \(\frac{3}{2}\) for the \(s\)-\(t\)-path TSP. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (2018) (to appear)

21. Vygen, J.: New approximation algorithms for the TSP. OPTIMA 90, 1–12 (2012)

    Google Scholar 

22. Vygen, J.: Reassembling trees for the traveling salesman. SIAM J. Discrete Math. 30, 875–894 (2016)

    Article  MathSciNet  Google Scholar 

Download references