Average-case approximation ratio of the 2-opt algorithm for the TSP

Average-case approximation ratio of the 2-opt algorithm for the TSP

0.00 Avg rating—0 Votes
Article ID: iaor20102941
Volume: 37
Issue: 2
Start Page Number: 83
End Page Number: 84
Publication Date: Mar 2009
Journal: Operations Research Letters
Authors: ,
Abstract:

We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly O(√n) for instances with n nodes, where the edge weights are drawn uniformly and independently at random.

Reviews

Required fields are marked *. Your email address will not be published.