An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem

by Chandra Chekuri and Martin Pál

Theory of Computing, Volume 3(10), pp. 197-209, 2007

Bibliography with links to cited articles

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin: Network Flows. Prentice Hall, 1993.
[2] Abraham Bachrach, Kevin Chen, Chris Harrelson, Radu Mihaescu, Satish Rao, and Apurva Shah: Lower bounds for maximum parsimony with gene order data. In Proc. 3rd RECOMB Satellite Workshop on Comparative Genomics (RCG'05), LNCS, pp. 1-10. Springer, 2005. [Springer:761n756g03752l46].
[3] Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In Proc. 36th STOC, pp. 166-174. ACM Press, 2004. [STOC:10.1145/1007352.1007385].
[4] Marcus Bläser: A new approximation algorithm for the asymmetric TSP with triangle inequality. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'02), pp. 638-645. SIAM, 2002. [SODA:644213].
[5] Avrim Blum, Shuchi Chawla, David Karger, Terran Lane, Adam Meyerson, and Maria Minkoff: Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal on Computing, 37:653-670, 2007. [SICOMP:10.1137/050645464].
[6] Moses Charikar, Michel Goemans, and Howard Karloff: On the integrality ratio for asymmetric TSP. In Proc. 45th FOCS, pp. 101-107. IEEE Computer Society, 2004. [FOCS:10.1109/FOCS.2004.45].
[7] Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, and Craig Silverstein: Constrained TSP and lower power computing. In Proc. First Workshop on Algorithms and Data Structures (WADS'97), pp. 104-115, 1997. [WADS:d5764136r2147633].
[8] Chandra Chekuri, Nitish Korula, and Martin Pál: Improved algorithms for orienteering and related problems. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'08). SIAM, 2008. To appear.
[9] Chandra Chekuri and Martin Pál: A recursive greedy algorithm for walks in directed graphs. In Proc. 46th FOCS, pp. 245-253. IEEE Computer Society, 2005. [FOCS:10.1109/SFCS.2005.9].
[10] Nicos Christofides: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, CMU, 1976.
[11] Vašek Chvátal: A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4:233-235, 1979.
[12] Uriel Feige and Mohit Singh: Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In Proc. 10th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'07), volume 4627 of LNCS, pp. 104-118. Springer, 2007. [Springer:u201633r5096547w].
[13] Alan Frieze, G. Galbiati, and M. Maffioli: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12:23-39, 1982. [doi:10.1002/net.3230120103]. [ DOI ]
[14] G. Gutin and A.P. Punnen, editors. Traveling Salesman Problem and Its Variations. Springer-Verlag, Berlin, 2002.
[15] N. Guttmann-Beck, R. Hassin, S. Khuller, and B. Raghavachari: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica, 28:422-437, 2000. Preliminary version in Proc.of FSTTCS, 1998. [Algorithmica:38vtl0dhpg55l0au].
[16] J. Hoogeveen: Analysis of Christofides' heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10(5):291-295, 1991. [Elsevier:10.1016/0167-6377(91)90016-I].
[17] H. Kaplan, M. Lewenstein, N. Shafir, and M. Sviridenko: Approximation algorithms for asymmetric TSP by decomposing directed regular multidigraphs. Journal of the ACM, 52:602-626, 2005. [JACM:10.1145/1082036.1082041].
[18] Jon Kleinberg and David Williamson: Unpublished note. 1998.
[19] Fumei Lam and Alantha Newman: Traveling salesman path problems. Mathematical Programming A, 2006. Online publication date 1 Nov 2006. [Springer:7773743425mx673l].
[20] E. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D. Shmoys, editors. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons Ltd., 1985.
[21] V. Nagarajan and R. Ravi: Poly-logarithmic approximation algorithms for directed vehicle routing problems. In Proc. 10th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'07), volume 4627 of LNCS, pp. 257-270. Springer, 2007. [Springer:vn2516l2l015u7u1].
[22] P. Toth and D. Vigo, editors. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2002.
[23] David Williamson: Analysis of the held-karp heuristic for the traveling salesman problem. Master's thesis, MIT Computer Science Department, 1990. [ http ]
[24] David Williamson: Lecture notes on approximation algorithms. Technical Report RC 21273, IBM, February 1999.
[25] N. Young, R. Tarjan, and J. Orlin: Faster parametric shortest path and minimum balance algorithms. Networks, 21(2):205-221, 1991. [doi:10.1002/net.3230210206, arXiv:cs/0205041]. [ DOI ]

This file has been generated by bibtex2html 1.85.