Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a polynomial time factor 0.999 ċ log n approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Piotr Berman , Marek Karpinski, 8/7-approximation algorithm for (1,2)-TSP, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.641-648, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109627]
• 3: Bläser, M. 2004. A 3/4-approximation algorithm for MaxATSP with weights zero and one. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). Lecture Notes in Computer Science, vol. 3122. 61--71.
• 4: Bläser, M., and Manthey, B. 2005. Approximating maximum weight cycle covers in directed graphs with edge weights zero and one. Algorithmica 41, 2, 121--139.
• 5: Bläser, M., Manthey, B., and Sgall, J. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algor. To appear.
• 6: Hans-Joachim Böckenhauer , Juraj Hromkovic , Ralf Klasing , Sebastian Seibert , Walter Unger, An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.382-394, February 01, 2000
• 7: L. Sunil Chandran , L. Shankar Ram, Approximations for ATSP with Parametrized Triangle Inequality, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.227-237, March 14-16, 2002
• 8: Christofides, N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. In Algorithms and Complexity: New Directions and Recent Results, J. F. Traub, Ed. Academic Press, 441.
• 9: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 10: Frieze, A. M., Galbiati, G., and Maffioli, F. 1982. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12, 1, 23--39.
• 11: R. L. Graham , M. Grötschel , L. Lovász, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 12: Johnson, D. S. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci 9, 256--278.
• 13: Johnson, D. S., Gutin, G., McGeoch, L. A., Yeo, A., Zhang, W., and Zverovitch, A. 2002. Experimental analysis of heuristics for the ATSP. In The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen, Eds. Combinatorial Optimization, vol. 12. Kluwer.
• 14: Haim Kaplan , Moshe Lewenstein , Nira Shafrir , Maxim Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs, Journal of the ACM (JACM), v.52 n.4, p.602-626, July 2005 [doi>10.1145/1082036.1082041]
• 15: Karp, R. M. 1978. A characterization of the minimum cycle mean in a digraph. Discrete Math. 23, 309--311.
• 16: Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., and Shmoys, D. B., Eds. 1985. The Traveling Salesman Problem. Wiley.
• 17: Moshe Lewenstein , Maxim Sviridenko, A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP, SIAM Journal on Discrete Mathematics, v.17 n.2, p.237-248, 2004 [doi>10.1137/S0895480102402861]
• 18: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 19: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
• 20: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 21: Williamson, D. P. 1999. Lecture notes on approximation algorithms. Tech. rep. RC 21409, IBM T. J. Watson Research Center.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithm, TSP, cycle cover, traveling salesman problem