35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality

1. Bläser, M., Ram, S., Sviridenko, M.: Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. In: Proc. 9th Workshop on Algorithms and Data Structures (WADS 2005). Lecture Notes in Computer Science, vol. 3122, pp. 350–359. Springer, Berlin (2005)

   Chapter  Google Scholar 

2. Bläser, M.: An 8/13-approximation algorithm for the asymmetric maximum tsp. J. Algorithms 50(1), 23–48 (2004)

   Article  MATH  MathSciNet  Google Scholar 

3. Hassin, R., Rubinstein, S.: Better approximations for max TSP. Inf. Process. Lett. 75(4), 181–186 (2000)

   Article  MATH  MathSciNet  Google Scholar 

4. Hassin, R., Rubinstein, S.: A 7/8-approximation algorithm for metric Max TSP. Inf. Process. Lett. 81(5), 247–251 (2002)

   Article  MATH  MathSciNet  Google Scholar 

5. Rao Kosaraju, S., Park, J.K., Stein, C.: Long tours and short superstrings (preliminary version). In: Proc. 39th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS 1994), pp. 166–177 (1994)

6. Lewenstein, M., Sviridenko, M.: A 5/8 approximation algorithm for the maximum asymmetric TSP. SIAM J. Discrete Math. 17(2), 237–248 (2003)

   Article  MATH  MathSciNet  Google Scholar 

7. Kostochka, A.V., Serdyukov, A.I.: Polynomial algorithms with the estimates 3/4 and 5/6 for the traveling salesman problem of the maximum. Upr. Sist. 26, 55–59 (1985) (in Russian)

   MathSciNet  Google Scholar 

8. Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602–626 (2005)

   Article  MathSciNet  Google Scholar 

9. Chen, Z.-Z., Nagoya, T.: Improved approximation algorithms for metric Max TSP. In: Proc. 13th Annual European Symposium on Algorithms (ESA’05). Lecture Notes in Computer Science, vol. 3669, pp. 179–190. Springer, Berlin (2005)

   Google Scholar 

10. Lovász, L., Plummer, M.D.: Matching Theory. Elsevier, Amsterdam (1986)

    MATH  Google Scholar 

11. Bläser, M., Manthey, B.: Two approximation algorithms for 3-cycle covers. In: Proc. 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2002). Lecture Notes in Computer Science, vol. 2462, pp. 40–50. Springer, Berlin (2002)

    Chapter  Google Scholar 

Download references