An 8/13-approximation algorithm for the asymmetric maximum TSP

ABSTRACT

We present a polynomial time approximation algorithm for the asymmetric maximum traveling salesperson problem that achieves performance ratio 8/13(1 - 1/n). The running time of our algorithm is O(n³).

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: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 3: Alexander I. Barvinok , David S. Johnson , Gerhard J. Woeginger , Russell Woodroofe, The Maximum Traveling Salesman Problem Under Polyhedral Norms, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.195-201, June 22-24, 1998
• 4: Markus Bläser , Bodo Siebert, Computing Cycle Covers without Short Cycles, Proceedings of the 9th Annual European Symposium on Algorithms, p.368-379, August 28-31, 2001
• 5: Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis, Linear approximation of shortest superstrings, Journal of the ACM (JACM), v.41 n.4, p.630-647, July 1994 [doi>10.1145/179812.179818]
• 6: Dany Breslauer , Tao Jiang , Zhigen Jiang, Rotations of periodic strings and short superstrings, Journal of Algorithms, v.24 n.2, p.340-353, Aug. 1997 [doi>10.1006/jagm.1997.0861]
• 7: Robert D. Carr , Santosh Vempala, Towards a 4/3 approximation for the asymmetric traveling salesman problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.116-125, January 09-11, 2000, San Francisco, California, United States
• 8: N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, page 441. Academic Press, 1976.
• 9: Lars Engebretsen , Marek Karpinski, Approximation Hardness of TSP with Bounded Metrics, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.201-212, July 08-12, 2001
• 10: M. L. Fisher, L. Nemhauser, and L. A. Wolsey. An analysis of approximations for finding a maximum weight Hamiltonian circuit. Networks, 12(1):799-809, 1979.
• 11: A. M. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1):23-39, 1982.
• 12: Refael Hassin , Shlomi Rubinstein, An approximation algorithm for the maximum traveling salesman problem, Information Processing Letters, v.67 n.3, p.125-130, Aug. 17, 1998 [doi>10.1016/S0020-0190(98)00102-1]
• 13: Refael Hassin , Shlomi Rubinstein, Better approximations for max TSP, Information Processing Letters, v.75 n.4, p.181-186, Sept. 30, 2000 [doi>10.1016/S0020-0190(00)00097-1]
• 14: Refael Hassin , Shlomi Rubinstein, A 7/8-Approximation Algorithm for Metric Max TSP, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.205-209, August 08-10, 2001
• 15: S. R. Kosaraju, J. K. Park, and C. Stein. Long tours and short superstrings. In Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), 1994.
• 16: A. V. Kostochka and A. I. Serdyukov. Polynomial algorithms with the estimates 3/4 and 5/6 for the traveling salesman problem of the maximum. Upravlyaemye Sistemy, 26:55-59, 1985. (in Russian).
• 17: E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem. Wiley, 1985.
• 18: 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]
• 19: A. I. Serdyukov. An algorithm with an estimate for the traveling salesman problem of the maximum. Upravlyaemye Sistemy, 25:80-86, 1984. (in Russian).
• 20: Z. Sweedyk, \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring, SIAM Journal on Computing, v.29 n.3, p.954-986, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539796324661]
• 21: J. Tarhio , E. Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings, Theoretical Computer Science, v.57 n.1, p.131-145, April 1988 [doi>10.1016/0304-3975(88)90167-3]
• 22: J. S. Turner, Approximation algorithms for the shortest common superstring problem, Information and Computation, v.83 n.1, p.1-20, Oct. 1989 [doi>10.1016/0890-5401(89)90044-8]