35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality | SpringerLink
Skip to main content
Springer Nature Link
Log in

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

(Extended Abstract)

  • Conference paper
Algorithms and Data Structures (WADS 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4619))

Included in the following conference series:

Abstract

We describe a new approximation algorithm for the asymmetric maximum traveling salesman problem (ATSP) with triangle inequality. Our algorithm achieves approximation factor 35/44 which improves on the previous 31/40 factor of Bläser, Ram and Sviridenko [2].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bläser, M., Manthey, B.: Two approximation algorithms for 3-cycle covers. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 40–50. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  2. Bläser, M., Ram, S., Sviridenko, M.: Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 350–359. Springer, Heidelberg (2005)

    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. 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 

  6. Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings (preliminary version). In: FOCS 1994, pp. 166–177 (1994)

    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 (in Russian). Upravlyaemye Sistemy 26, 55–59 (1985)

    MathSciNet  Google Scholar 

  8. 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 

  9. Serdyukov, A.I.: The traveling salesman problem of the maximum (in Russian). Upravlyaemye Sistemy 25, 80–86 (1984)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, Warsaw University, Warsaw, Poland

    Łukasz Kowalik & Marcin Mucha

Authors
  1. Łukasz Kowalik
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcin Mucha
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Dehne Jörg-Rüdiger Sack Norbert Zeh

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kowalik, Ł., Mucha, M. (2007). 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_51

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73951-7_51

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73948-7

  • Online ISBN: 978-3-540-73951-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation