{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:12:16Z","timestamp":1725498736553},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540772934"},{"type":"electronic","value":"9783540772941"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77294-1_10","type":"book-chapter","created":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T04:54:07Z","timestamp":1197608047000},"page":"99-111","source":"Crossref","is-referenced-by-count":6,"title":["Improving the Efficiency of Helsgaun\u2019s Lin-Kernighan Heuristic for the Symmetric TSP"],"prefix":"10.1007","author":[{"given":"Dirk","family":"Richter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Goldengorin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerold","family":"J\u00e4ger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Molitor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","volume":"15","author":"D. Applegate","year":"2003","unstructured":"Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for Large Traveling Salesman Problems. INFORMS J. Comput.\u00a015(1), 82\u201392 (2003)","journal-title":"INFORMS J. Comput."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1287\/ijoc.13.1.56.9748","volume":"13","author":"E. Balas","year":"2001","unstructured":"Balas, E., Simonetti, N.: Linear Time Dynamic Programming Algorithms for New Classes of Restricted TSPs: A Computational Study. INFORMS J. Comp.\u00a013, 56\u201375 (2001)","journal-title":"INFORMS J. Comp."},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(88)90057-1","volume":"20","author":"M. Chrobak","year":"1988","unstructured":"Chrobak, M., Poljak, S.: On Common Edges in Optimal Solutions to the Traveling Salesman and Other Optimization Problems. Discrete Appl. Math.\u00a020(2), 101\u2013111 (1988)","journal-title":"Discrete Appl. Math."},{"key":"10_CR4","unstructured":"Climer, S., Zhang, W.: Searching for Backbones and Fat: A Limit-Crossing Approach with Applications. In: AAAI-02, American Association for Artificial Intelligence. Proceedings of the 18th National Conference on Artificial Intelligence (2002), \n                    \n                      www.aaai.org"},{"issue":"3","key":"10_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W. Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour Merging via Branch-Decomposition. INFORMS J. Comput.\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ejor.2004.04.023","volume":"160","author":"D. Gamboa","year":"2005","unstructured":"Gamboa, D., Rego, C., Glover, F.: Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems. European Journal Oper. Res.\u00a0160(1), 154\u2013171 (2005)","journal-title":"European Journal Oper. Res."},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1016\/j.cor.2005.06.014","volume":"33","author":"D. Gamboa","year":"2006","unstructured":"Gamboa, D., Rego, C., Glover, F.: Implementation Analysis of Efficient Heuristic Algorithms for the Traveling Salesman Problem. Comput. Oper. Res.\u00a033(4), 1154\u20131172 (2006)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"10_CR8","first-page":"52","volume":"10","author":"D. Ghosh","year":"2007","unstructured":"Ghosh, D., Goldengorin, B., Gutin, G., J\u00e4ger, G.: Improving the Performance of Greedy Heuristics for TSPs Using Tolerances. Communications in Dependability and Quality Management\u00a010(1), 52\u201370 (2007)","journal-title":"Communications in Dependability and Quality Management"},{"key":"10_CR9","unstructured":"Goldengorin, B., J\u00e4ger, G.: How to Make a Greedy Heuristic for the Asymmetric Traveling Salesman Problem Competitive. SOM (Systems, Organisations and Management) Research Report 05A11, University Groningen, The Netherlands (2005)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/11775096_19","volume-title":"Algorithmic Aspects in Information and Management","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Some Basics on Tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 194\u2013206. Springer, Heidelberg (2006)"},{"issue":"9","key":"10_CR11","doi-asserted-by":"publisher","first-page":"716","DOI":"10.3844\/jcssp.2006.716.734","volume":"2","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Tolerances Applied in Combinatorial Optimization. J. Comput. Sci.\u00a02(9), 716\u2013734 (2006)","journal-title":"J. Comput. Sci."},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/11922377_8","volume-title":"Combinatorial and Algorithmic Aspects of Networking","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP. In: Erlebach, T. (ed.) CAAN 2006. LNCS, vol.\u00a04235, pp. 86\u201397. Springer, Heidelberg (2006)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-540-30559-0_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Goldengorin","year":"2004","unstructured":"Goldengorin, B., Sierksma, G., Turkensteen, M.: Tolerance Based Algorithms for the ATSP. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 222\u2013234. Springer, Heidelberg (2004)"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0305-0548(98)00064-1","volume":"26","author":"G. Gutin","year":"1999","unstructured":"Gutin, G.: Exponential Neighborhood Local Search for the Traveling Salesman Problem. Comput. Oper. Res.\u00a026, 313\u2013320 (1999)","journal-title":"Comput. Oper. Res."},{"issue":"5-6","key":"10_CR15","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s10732-005-3487-y","volume":"11","author":"G. Gutin","year":"2005","unstructured":"Gutin, G., Glover, F.: Further Extension of the TSP Assign Neighborhood. Journal of Heuristics\u00a011(5-6), 501\u2013505 (2005)","journal-title":"Journal of Heuristics"},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K. Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal Oper. Res.\u00a0126(1), 106\u2013130 (2000)","journal-title":"European Journal Oper. Res."},{"key":"10_CR17","first-page":"215","volume-title":"Local Search in Combinatorial Optimization","author":"D. Johnson","year":"1997","unstructured":"Johnson, D., McGeoch, L.: The Traveling Salesman Problem: A Case Study in Local Optimization. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215\u2013310. John Wiley and Sons, Chichester (1997)"},{"issue":"6","key":"10_CR18","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1016\/j.orl.2004.04.001","volume":"32","author":"A.B. Kahng","year":"2004","unstructured":"Kahng, A.B., Reda, S.: Match Twice and Stitch: A New TSP Tour Construction Heuristic. Oper. Res. Lett.\u00a032(6), 499\u2013509 (2004)","journal-title":"Oper. Res. Lett."},{"key":"10_CR19","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(91)90044-W","volume":"30","author":"M. Libura","year":"1991","unstructured":"Libura, M.: Sensitivity Analysis for Minimum Hamiltonian Path and Traveling Salesman Problems. Discrete Appl. Math.\u00a030, 197\u2013211 (1991)","journal-title":"Discrete Appl. Math."},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An Effective Heuristic Algorithm for the Traveling Salesman Problem. Oper. Res.\u00a021, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"issue":"3","key":"10_CR21","first-page":"299","volume":"5","author":"O. Martin","year":"1991","unstructured":"Martin, O., Otto, S.W., Felten, E.W.: Large-Step Markov Chains for the Traveling Salesman Problem. Complex Systems\u00a05(3), 299\u2013326 (1991)","journal-title":"Complex Systems"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0167-6377(92)90028-2","volume":"11","author":"O. Martin","year":"1992","unstructured":"Martin, O., Otto, S.W., Felten, E.W.: Large-Step Markov Chains for the TSP Incorporating Local Search Heuristics. Oper. Res. Lett.\u00a011, 219\u2013224 (1992)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"10_CR23","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10107-003-0497-0","volume":"101","author":"J.B. Orlin","year":"2004","unstructured":"Orlin, J.B., Sharma, D.: Extended Neighborhood: Definition and Characterization. Math. Program., Ser. A\u00a0101(3), 537\u2013559 (2004)","journal-title":"Math. Program., Ser. A"},{"key":"10_CR24","unstructured":"Van der Poort, E.S.: Aspects of Sensitivity Analysis for the Traveling Salesman Problem. PhD Thesis, Department of Econometrics and Operations Research, University of Groningen, The Netherlands (1997)"},{"key":"10_CR25","unstructured":"Richter, D.: Toleranzen in Helsgauns Lin-Kernighan-Heuristik f\u00fcr das TSP. Diploma Thesis, Martin-Luther-University Halle-Wittenberg, Germany (2006)"},{"key":"10_CR26","unstructured":"Schilham, R.M.F.: Commonalities in Local Search. PhD Thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, The Netherlands (2001)"},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/3-540-45356-3_65","volume-title":"Parallel Problem Solving from Nature-PPSN VI","author":"T. St\u00fctzle","year":"2000","unstructured":"St\u00fctzle, T., Gr\u00fcn, A., Linke, S., R\u00fcttger, M.: A Comparison of Nature Inspired Heuristics on the Traveling Salesman Problem. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) Parallel Problem Solving from Nature-PPSN VI. LNCS, vol.\u00a01917, pp. 661\u2013670. Springer, Heidelberg (2000)"},{"key":"10_CR28","unstructured":"Tamaki, H.: Alternating Cycles Contribution: A Tour Merging Strategy for the Traveling Salesman Problem. Research Report MPI-I-2003-1-007, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (2003)"},{"key":"10_CR29","unstructured":"Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-Based Branch and Bound Algorithms for the ATSP. European Journal Oper. Res., 1\u201314 (to appear, 2007)"},{"issue":"5","key":"10_CR30","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1287\/opre.50.5.862.373","volume":"50","author":"C. Walshaw","year":"2002","unstructured":"Walshaw, C.: A Multilevel Approach to the Traveling Salesman Problem. Oper. Res.\u00a050(5), 862\u2013877 (2002)","journal-title":"Oper. Res."},{"issue":"1","key":"10_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.04.001","volume":"158","author":"W. Zhang","year":"2004","unstructured":"Zhang, W.: Configuration Landscape Analysis and Backbone Guided Local Search: Part I: Satisfiability and Maximum Satisfiability. Artificial Intelligence\u00a0158(1), 1\u201326 (2004)","journal-title":"Artificial Intelligence"},{"key":"10_CR32","unstructured":"Zhang, W., Looks, M.: A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones. In: Kaelbling, L.P., Saffiotti, A. (eds.) IJCAI 2005. Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 343\u2013350 (2005)"},{"key":"10_CR33","unstructured":"DIMACS Implementation Challenge: \n                    \n                      www.research.att.com\/~dsj\/chtsp\/"},{"key":"10_CR34","unstructured":"National Instances from the TSP Homepage: \n                    \n                      www.tsp.gatech.edu\/world\/summary.html"},{"key":"10_CR35","unstructured":"Source code of this paper. \n                    \n                      http:\/\/www.informatik.uni-halle.de\/ti\/forschung\/toleranzen\/quelltexte\/index.en.php"},{"key":"10_CR36","unstructured":"TSP Homepage: \n                    \n                      www.tsp.gatech.edu\/"},{"key":"10_CR37","unstructured":"VLSI Instances from the TSP Homepage: \n                    \n                      www.tsp.gatech.edu\/vlsi\/summary.html"},{"key":"10_CR38","unstructured":"World TSP from the TSP Homepage: \n                    \n                      www.tsp.gatech.edu\/world\/"}],"container-title":["Lecture Notes in Computer Science","Combinatorial and Algorithmic Aspects of Networking"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77294-1_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:07:56Z","timestamp":1619521676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77294-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540772934","9783540772941"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77294-1_10","relation":{},"subject":[]}}