首页 | 本学科首页   官方微博 | 高级检索  
     


Tight bounds for christofides' traveling salesman heuristic
Authors:G. Cornuejols  G. L. Nemhauser
Affiliation:(1) Cornell University, Ithaca, New York, USA
Abstract:Christofides [1] proposes a heuristic for the traveling salesman problem that runs in polynomial time. He shows that when the graphG = (V, E) is complete and the distance matrix defines a function onV × V that is metric, then the length of the Hamiltonian cycle produced by the heuristic is always smaller than 3/2 times the length of an optimal Hamiltonian cycle. The purpose of this note is to refine Christofides' worst-case analysis by providing a tight bound for everyn ge 3, wheren is the number of vertices of the graph. We also show that these bounds are still tight when the metric is restricted to rectilinear distances, or to Euclidean distances for alln ge 6.This work was supported, in part, by NSF Grant ENG 75-00568 to Cornell University. This work was done when the authors were affiliated with the Center for Operations Research and Econometrics, University of Louvain, Belgium.
Keywords:Traveling Salesman Problem  Heuristics
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号