TY - JOUR
T1 - An improved randomized approximation algorithm for max TSP
AU - Chen, Zhi-Zhong
AU - Wang, Lusheng
PY - 2005/6
Y1 - 2005/6
N2 - We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.
AB - We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.
KW - Approximation algorithms
KW - Graph algorithms
KW - Max TSP
KW - Randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=23944508242&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-23944508242&origin=recordpage
U2 - 10.1007/s10878-005-1779-7
DO - 10.1007/s10878-005-1779-7
M3 - 21_Publication in refereed journal
VL - 9
SP - 401
EP - 432
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 4
ER -