Journal
OPERATIONS RESEARCH LETTERS
Volume 43, Issue 3, Pages 259-261Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2015.02.009
Keywords
Traveling salesman problem; Greedy algorithm; Clarke-Wright savings heuristic; Approximation algorithm
Categories
Ask authors/readers for more resources
We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is Theta (log n). Moreover, we prove that the same result also holds for graphic, euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is (9 (log n). (C) 2015 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available