期刊
OPERATIONS RESEARCH LETTERS
卷 43, 期 3, 页码 259-261出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2015.02.009
关键词
Traveling salesman problem; Greedy algorithm; Clarke-Wright savings heuristic; Approximation algorithm
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据