Abstract
We present an O(n3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically \(\frac{251}{331}\), where n is the number of vertices in the input (undirected) graph. This improves the previous best.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A.I. Barvinok, D.S. Johnson, G.J. Woeginger, and R. Woodroofe, “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, vol. 1412, pp. 195–201, 1998.
P. Chalasani and R. Motwani, “Approximating Capacitated Routing and Delivery Problems,” SIAM Journal on Computing, vol. 28, pp. 2133–2149, 1999.
R. Hassin and S. Rubinstein, “An Approximation Algorithm for the Maximum Traveling Salesman Problem,” Information Processing Letters, vol. 67, pp. 125–130, 1998.
TSP,” Information Processing Letters, vol. 75, pp. 181–186, 2000.
TSP,” Information Processing Letters, vol. 81, pp. 247–251, 2002.
(in Russian),” Upravlyaemye Sistemy, vol. 26, pp. 55–59, 1985.
Author information
Authors and Affiliations
Corresponding author
Additional information
Part of work done while visiting City University of Hong Kong.
Rights and permissions
About this article
Cite this article
Chen, ZZ., Wang, L. An Improved Randomized Approximation Algorithm for Max TSP. J Comb Optim 9, 401–432 (2005). https://doi.org/10.1007/s10878-005-1779-7
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-005-1779-7