Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem |
| |
Authors: | Keld Helbig Hansen Jakob Krarup |
| |
Institution: | (1) Spadille, Inc., and Institute of Datalogy, University of Copenhagen, Denmark |
| |
Abstract: | A highly efficient algorithm (HK) devised by Held and Karp for solving the symmetric traveling-salesman problem was presented at the 7th Mathematical Programming Symposium in 1970 and published in Mathematical Programming in 1971. Its outstanding performance is due to a clever exploitation of the relationship between the traveling-salesman problem and minimum spanning trees.However, various improvements of their method have led to a version (IHK) which tends to be some 25 times faster than the original one. Experiments with data selected at random, ranging in size up to 80 cities, show that the computing time for IHK is roughly doubled as the number of cities is increased by 10. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|