{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:03:10Z","timestamp":1756425790001,"version":"3.44.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662273"},{"type":"electronic","value":"9783540485186"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48518-x_16","type":"book-chapter","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T13:57:15Z","timestamp":1195048635000},"page":"270-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Finding the Right Cutting Planes for the TSP"],"prefix":"10.1007","author":[{"given":"Matthew S.","family":"Levine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,4,19]]},"reference":[{"key":"16_CR1","first-page":"645","volume":"III","author":"D. Applegate","year":"1998","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal, and W. Cook. On the solution of traveling salesman problems. Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, ICM III:645\u2013656, 1998.","journal-title":"Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung"},{"unstructured":"C. C. Chekuri, A. V. Goldberg, D. R. Karger, M. S. Levine, and C. Stein. Experimental study of minimum cut algorithms. In Proceedings of the 8th\n                           Annual ACM-SIAM Symposium on Discrete Algorithms, pages 324\u2013333. ACM-SIAM, Jan. 1997. A longer version appears as the fourth author\u2019s Masters thesis, available as a MIT Lab for Computer Science tech report, MIT-LCS-TR-719.","key":"16_CR2"},{"issue":"4","key":"16_CR3","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R. E. Gomory","year":"1961","unstructured":"R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society of Industrial and Applied Mathematics, 9(4):551\u2013570, Dec. 1961.","journal-title":"Journal of the Society of Industrial and Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, 1988.","key":"16_CR4","DOI":"10.1007\/978-3-642-97881-4"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R. M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Res., 18:1138\u20131162, 1970.","journal-title":"Operations Res."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R. M. Karp. The traveling-salesman problem and minimum spanning trees: Part ii. Math. Programming, 1:6\u201325, 1971.","journal-title":"Math. Programming"},{"unstructured":"D. S. Johnson, L. A. McGeoch, and E. E. Rothberg. Asymptotic experimental analysis for the held-karp traveling salesman bound. In Proceedings of the 7th\n                           Annual ACM-SIAM Symposium on Discrete Algorithms, pages 341\u2013350, 1996.","key":"16_CR7"},{"unstructured":"M. J\u00fcnger, G. Rinaldi, and S. Thienel. Practical performance of efficient minimum cut algorithms. Technical report, Informatik, Universit\u00e4t zu K\u00f6ln, 1997.","key":"16_CR8"},{"doi-asserted-by":"crossref","unstructured":"D. R. Karger. Minimum cuts in near-linear time. In G. Miller, editor, Proceedings of the 28th\n                           ACM Symposium on Theory of Computing, pages 56\u201363. ACM, ACM Press, May 1996.","key":"16_CR9","DOI":"10.1145\/237814.237829"},{"issue":"4","key":"16_CR10","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D. R. Karger","year":"1996","unstructured":"D. R. Karger and C. Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601\u2013640, July 1996. Preliminary portions appeared in SODA 1992 and STOC 1993.","journal-title":"Journal of the ACM"},{"unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem. John Wiley & Sons, 1985.","key":"16_CR11"},{"key":"16_CR12","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"G. Reinelt. TSPLIB\u2014a traveling salesman problem library. ORSA J. Comput., 3:376\u2013384, 1991.","journal-title":"ORSA J. Comput."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D. B. Shmoys","year":"1990","unstructured":"D. B. Shmoys and D. P. Williamson. Analyzing the held-karp tsp bound: A monotonicity property with applications. Inform. Process. Lett., 35:281\u2013285, 1990.","journal-title":"Inform. Process. Lett."},{"key":"16_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/3-540-55719-9_88","volume-title":"Automata, Languages and Programming. 19thInternational Colloquium Proceedings","author":"V. V. Vazirani","year":"1992","unstructured":"V. V. Vazirani and M. Yannakakis. Suboptimal cuts: Their enumeration, weight, and number. In Automata, Languages and Programming. 19th\n                           International Colloquium Proceedings, volume 623 of Lecture Notes in Computer Science, pages 366\u2013377. Springer-Verlag, July 1992."},{"key":"16_CR15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L. Wolsey","year":"1980","unstructured":"L. Wolsey. Heuristic analysis, linear programming, and branch and bound. Math. Prog. Study, 13:121\u2013134, 1980.","journal-title":"Math. Prog. Study"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experimentation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48518-X_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T07:51:08Z","timestamp":1756367468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48518-X_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662273","9783540485186"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-48518-x_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"19 April 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}