An Analysis of Several Heuristics for the Traveling Salesman Problem

作     者：Daniel J. Rosenkrantz Richard E. Stearns Philip M. Lewis, II 

出 版 物：《SIAM Journal on Computing》 

年 卷 期：1977年第6卷第3期

页      面：563-581页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：traveling salesman problem approximation algorithm -optimal minimal spanning tree triangle inequality 

摘      要：Several polynomial time algorithms finding “good, but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any n8 role=presentationn≧8span style=display: inline-block; overflow: hidden; vertical-align: -0.265em