Abstract
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is \(\frac{27}{35}\). The other is for undirected graphs and its approximation ratio is \(\frac{7}{8}-o(1)\). Both algorithms improve on the previous bests.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barvinok AI, Johnson DS, Woeginger GJ, Woodroofe R (1998) Finding maximum length tours under polyhedral norms. Proceedings of the Sixth International Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 1412:195–201
Chen ZZ, Wang L (2005) An improved randomized approximation algorithm for Max TSP. J Comb Optim 9:401–432
Chen ZZ, Okamoto Y, Wang L (2005) Improved deterministic approximation algorithms for Max TSP. Inf Process Lett 95:333–342
Hassin R, Rubinstein S (2002) A 7/8-Approximation approximations for metric Max TSP. Inf Process Lett 81:247–251
Kaplan H, Lewenstein M, Shafrir N, Sviridenko M (2003) Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Proceeding of the 44th Annual IEEE Symposium on Foundations Computer Science pp 56–75
Karp RM, Upfal E, Wigderson A (1986) Constructing a perfect matching is in random NC. Combinatorica 6:35–48
Kostochka AV, Serdyukov AI (1985) Polynomial algorithms with the estimates \(\frac{3}{4}\) and \(\frac{5}{6}\) for the traveling salesman problem of maximum (in Russian). Upravlyaemye Sistemy 26:55–59
Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Combinatorica 7:105–113
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the Proceedings of 13th European Symposium on Algorithms (ESA2005), Lecture Notes in Computer Science, Vol. 3669, pp. 179–190, 2005.
Rights and permissions
About this article
Cite this article
Chen, ZZ., Nagoya, T. Improved approximation algorithms for metric MaxTSP. J Comb Optim 13, 321–336 (2007). https://doi.org/10.1007/s10878-006-9023-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9023-7