LIU Jian-ping. Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane[J]. Journal of East China University of Science and Technology, 2004, (3): 336-338.
Citation:
LIU Jian-ping. Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane[J]. Journal of East China University of Science and Technology, 2004, (3): 336-338.
LIU Jian-ping. Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane[J]. Journal of East China University of Science and Technology, 2004, (3): 336-338.
Citation:
LIU Jian-ping. Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane[J]. Journal of East China University of Science and Technology, 2004, (3): 336-338.
Performance Ratio Analysis of the Nearest Neighbor Algorithm of TSP in Euclidean Plane
The performance ratio of the nearest neighbor algorithm of traveling salesman problem has been shown to have an upper bound above by a logarithmic function of the number of nodes. In this paper, we provide a logarithmic lower bound on the worst case in Euclidean plane.
DownLoad: