{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T21:18:38Z","timestamp":1790284718324,"version":"4.1.0"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.<\/jats:p>","DOI":"10.1137\/s0097539793251244","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1998-2029","source":"Crossref","is-referenced-by-count":88,"title":["New Results on the Old\n                    <i>k<\/i>\n                    -opt Algorithm for the Traveling Salesman Problem"],"prefix":"10.1137","volume":"28","author":[{"given":"Barun","family":"Chandra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Craig","family":"Tovey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon and Y. Azar,\n                      On\u2010line Steiner trees in the Euclidean plane\n                      , in Proc. 8th ACM Symposium on Computational Geometry, Berlin, 1992, pp. 337\u2013343.","DOI":"10.1145\/142675.142744"},{"key":"R2","unstructured":"J. L. Bentley, Invited talk at the 1st SIAM Symposium on Discrete Algorithms, San Francisco, 1990."},{"key":"R3","unstructured":"J. L. Bentley and J. Saxe,\n                      An analysis of two heuristics for the Euclidean traveling salesman problem\n                      , in Proc. 18th Allerton Conference on Communication, Control and Computing, Urbana\u2010Champaign, IL, 1980, pp. 41\u201349."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Simonovits, Paul Erdo\u02dds\u2019 influence on extremal graph theory, Algorithms Combin., Vol. 14, Springer, Berlin, 1997, 148\u201319297h:05092","DOI":"10.1007\/978-3-642-60406-5_15"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan, and J. Soares,\n                      New sparseness results on graph spanners\n                      , in Proc. 8th ACM Symposium on Computational Geometry, Berlin, 1992, pp. 192\u2013201.","DOI":"10.1145\/142675.142717"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90049-9"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"R8","unstructured":"R. Karp, J. Steele, Probabilistic analysis of heuristics, Wiley\u2010Intersci. Ser. Discrete Math., Wiley, Chichester, 1985, 181\u2013205811473"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587089"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. W. Krentel,\n                      Structure in locally optimal solutions\n                      , in Proc. 30th Symposium on Foundations of Computer Science, Research Triangle Park, NC, 1989, pp. 216\u2013221.","DOI":"10.1109\/SFCS.1989.63481"},{"key":"R11","unstructured":"M. W. Krentel, personal communication, Rice University, Houston, TX."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-9659(99)00181-0"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1142\/3139"},{"key":"R15","unstructured":"G. Lueker, Unpublished manuscript, Princeton University, Princeton, NJ, 1975."},{"key":"R16","volume-title":"Combinatorial optimization: algorithms and complexity","author":"Papadimitriou Christos","year":"1982"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300004083"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793251244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:30Z","timestamp":1787335950000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793251244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539793251244"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793251244","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}