{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:24:12Z","timestamp":1774355052103,"version":"3.50.1"},"publisher-location":"Dordrecht","reference-count":16,"publisher":"Springer Netherlands","isbn-type":[{"value":"9781402096877","type":"print"},{"value":"9781402096884","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-1-4020-9688-4_3","type":"book-chapter","created":{"date-parts":[[2009,4,20]],"date-time":"2009-04-20T10:15:15Z","timestamp":1240222515000},"page":"45-69","source":"Crossref","is-referenced-by-count":29,"title":["An analysis of several heuristics for the\u00a0traveling salesman problem"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Rosenkrantz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"II","given":"Philip M.","family":"Lewis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/opre.16.3.538","volume":"16","author":"M. Bellmore","year":"1968","unstructured":"M. Bellmore and G.\u00a0L. Nemhauser. The traveling salesman problem: A\u00a0survey. Operations Res., 16:538\u2013558, 1968.","journal-title":"Operations Res."},{"key":"3_CR2","volume-title":"Symp. on New Directions and Recent Results in Algorithms and Complexity","author":"N. Christofides","year":"1976","unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. In Symp. on New Directions and Recent Results in Algorithms and Complexity. Carnegie-Mellon Univ., Pittsburgh, 1976."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1287\/opre.6.6.791","volume":"6","author":"G.\u00a0A. Croes","year":"1958","unstructured":"G.\u00a0A. Croes. A method for solving traveling salesman problems. Operations Res., 6:791\u2013812, 1958.","journal-title":"Operations Res."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. Floyd","year":"1962","unstructured":"R. Floyd. Algorithm 97, Shortest path. Comm. ACM, 5:345, 1962.","journal-title":"Comm. ACM"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1287\/mnsc.11.8.B166","volume":"11","author":"J. Gavett","year":"1965","unstructured":"J. Gavett. Three heuristic rules for sequencing jobs to a single production facility. Management Sci., 11:166\u2013176, 1965.","journal-title":"Management Sci."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1287\/opre.10.5.647","volume":"10","author":"W.\u00a0W. Hardgrave","year":"1962","unstructured":"W.\u00a0W. Hardgrave and G.\u00a0L. Nemhauser. On the relation between the traveling salesman and the longest path problem. Operations Res., 10:647\u2013657, 1962.","journal-title":"Operations Res."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1287\/mnsc.10.2.225","volume":"10","author":"L.\u00a0L. Karg","year":"1964","unstructured":"L.\u00a0L. Karg and G.\u00a0L. Thompson. A heuristic approach to solving traveling salesman problems. Management Sci., 10:225\u2013248, 1964.","journal-title":"Management Sci."},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.\u00a0M. Karp","year":"1972","unstructured":"R.\u00a0M. Karp. Reducibility among combinatorial problems. In R.\u00a0E. Miller and J.\u00a0W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum, New York, 1972."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"2","author":"J.\u00a0B. Kruskal","year":"1956","unstructured":"J.\u00a0B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 2:48\u201350, 1956.","journal-title":"Proc. Amer. Math. Soc."},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin. Computer solution of the traveling salesman problem. Bell System Tech. J., 44:2245\u20132269, 1965.","journal-title":"Bell System Tech. J."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"S. Lin and B.\u00a0W. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Res., 21:498\u2013516, 1973.","journal-title":"Operations Res."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1093\/imamat\/3.4.362","volume":"3","author":"T.\u00a0A.\u00a0J. Nicholson","year":"1967","unstructured":"T.\u00a0A.\u00a0J. Nicholson. A sequential method for discrete optimization problems and its application to the assignment, traveling salesman, and three machine scheduling problems. J. Inst. Math. Appl., 3:362\u2013375, 1967.","journal-title":"J. Inst. Math. Appl."},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.\u00a0C. Prim","year":"1957","unstructured":"R.\u00a0C. Prim. Shortest connection networks and some generalizations. Bell System Tech. J., 36:1389\u20131401, 1957.","journal-title":"Bell System Tech. J."},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/0113056","volume":"13","author":"S. Reiter","year":"1965","unstructured":"S. Reiter and G. Sherman. Discrete optimizing. J. Soc. Indust. Appl. Math., 13:864\u2013889, 1965.","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1287\/mnsc.13.3.269","volume":"13","author":"S.\u00a0M. Roberts","year":"1966","unstructured":"S.\u00a0M. Roberts and B. Flores. An engineering approach to the traveling salesman problem. Management Sci., 13:269\u2013288, 1966.","journal-title":"Management Sci."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"S. Sahni and T. Gonzales. P-complete problems and approximate solutions. In IEEE Fifteenth Ann. Symp. on Switching and Automata Theory, pages 28\u201332, 1974.","DOI":"10.1109\/SWAT.1974.22"}],"container-title":["Fundamental Problems in Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4020-9688-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T19:10:22Z","timestamp":1580325022000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4020-9688-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9781402096877","9781402096884"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-1-4020-9688-4_3","relation":{},"subject":[],"published":{"date-parts":[[2009]]}}}