On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

References

• Adleman L. M. Molecular computation of solutions to combinatorial problems. Science (1994) 266:1021–1024Crossref, Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W., Helsgaun K. The traveling salesman problem homepage. . http://www.tsp.gatech.eduGoogle Scholar
• Arora S. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. Assocation Comput. Machinery (1998) 45(5):753–782Crossref, Google Scholar
• Bläser M. A new approximation algorithm for the asymmetric TSP with triangle inequality. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (2003) Baltimore, MD:638–645Google Scholar
• Boyd S., Elliott P. Finding the exact integrality gap for small ATSP’s. Combinatorial Optimisation Conference (CO2004) (2004) Lancaster, EnglandGoogle Scholar
• Boyd S., Labonté G. Finding the exact integrality gap for small traveling salesman problems. Proc. 9th Conf. Integer Programming Combin. Optim. (2002) 83–92Google Scholar
• Boyd S., Pulleyblank W. R. Optimizing over the subtour polytope of the traveling salesman problem. Math. Programming (1990) 49:163–187Crossref, Google Scholar
• Carr R., Vempala S. Towards a 4/3 approximation algorithm for the asymmetric TSP. Math. Programming (2004) 100:569–587Crossref, Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. (1976) . Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PAGoogle Scholar
• Dorigo M., Maniezzo V., Colorni A. The ant system: Optimization by a colony of cooperating agents. IEEE Trans. Systems, Man, Cybernetics, Part B (1996) 26:29–41Crossref, Google Scholar
• Frieze A. M., Galbiati G., Maffioli M. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks (1992) 12:23–39Crossref, Google Scholar
• Goemans M. X., Bertsimas D. Survivable networks, linear programming relaxations and the parsimonious property. Math. Programming (1993) 60:145–166Crossref, Google Scholar
• Held M., Karp R. M. The traveling salesman problem and minimum spanning trees. Oper. Res. (1970) 18:1138–1162Link, Google Scholar
• Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees: Part II. Math. Programming (1971) 1:6–25Crossref, Google Scholar
• Johnson D. S. Personal communication. (2004) Google Scholar
• Johnson D. S., McGeoch L. A., Gutin G., Punnen A. Experimental analysis of heuristics for the STSP. The Traveling Salesman Problem and its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 369–443Google Scholar
• Johnson D. S., McGeoch L. A., Rothberg E. E. Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Proc. 7th ACM-SIAM Sympos. Discrete Algorithms (1996) 341–350Google Scholar
• Johnson D. S., Gutin G., McGeoch L. A., Yeo A., Zhang W., Zverovich A., Gutin G., Punnen A. Experimental analysis of heuristics for the ATSP. The Traveling Salesman Problem and its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 445–487Google Scholar
• Kaplan H., Lewenstein M., Shafir N., Sviridenko M. Approximation algorithms for asymmetric TSP by decomposing directed regular multidigraphs. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci. (2003) Cambridge, MA:56–67Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) (John Wiley & Sons Ltd.)Google Scholar
• Mitchell J. S. B. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. (1999) 28:1298–1309Crossref, Google Scholar
• Monma C., Munson B., Pulleyblank W. Minimum-weight two-connected spanning networks. Math. Programming (1990) 46:153–171Crossref, Google Scholar
• Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. (1989) . Report 790, Caltech Concurrent Computation Program, Pasadena, CAGoogle Scholar
• Papadimitriou C. H., Vempala S. On the approximability of the traveling salesman problem. Proc. 32nd Annual ACM Sympos. Theory Comput. (2000) Portland, OR:126–133Google Scholar
• Shmoys D., Williamson D. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inform. Processing Lett. (1990) 35:281–285Crossref, Google Scholar
• Williamson D. P. Analysis of the Held-Karp heuristic for the traveling salesman problem. (1990) . M.S. thesis, Massachusetts Institute of TechnologyGoogle Scholar
• Wolsey L. A. Heuristic analysis, linear programming and branch and bound. Math. Programming Stud. (1980) 13:121–134Crossref, Google Scholar