{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T17:23:57Z","timestamp":1775064237994,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,6,19]],"date-time":"2013-06-19T00:00:00Z","timestamp":1371600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2013,6,19]],"date-time":"2013-06-19T00:00:00Z","timestamp":1371600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on \u201creal world\u201d Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every<jats:inline-formula><jats:tex-math>$p\\in\\mathbb{N}$<\/jats:tex-math><\/jats:inline-formula>, a family of<jats:italic>L<\/jats:italic><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>instances on which 2-Opt can take an exponential number of steps.<\/jats:p><jats:p>Previous probabilistic analyses were restricted to instances in which<jats:italic>n<\/jats:italic>points are placed uniformly at random in the unit square [0,1]<jats:sup>2<\/jats:sup>, where it was shown that the expected number of steps is bounded by<jats:inline-formula><jats:tex-math>$\\tilde{O}(n^{10})$<\/jats:tex-math><\/jats:inline-formula>for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1]<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>, for an arbitrary<jats:italic>d<\/jats:italic>\u22652. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number<jats:italic>n<\/jats:italic>of points and the maximal density<jats:italic>\u03d5<\/jats:italic>of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of<jats:inline-formula><jats:tex-math>$\\tilde{O}(n^{4+1\/3}\\cdot\\phi^{8\/3})$<\/jats:tex-math><\/jats:inline-formula>. When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to<jats:inline-formula><jats:tex-math>$\\tilde{O}(n^{4+1\/3-1\/d}\\cdot\\phi^{8\/3})$<\/jats:tex-math><\/jats:inline-formula>. If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by<jats:inline-formula><jats:tex-math>$\\tilde{O}(n^{4-1\/d}\\cdot\\phi)$<\/jats:tex-math><\/jats:inline-formula>. In addition, we prove an upper bound of<jats:inline-formula><jats:tex-math>$O(\\sqrt[d]{\\phi})$<\/jats:tex-math><\/jats:inline-formula>on the expected approximation factor with respect to all<jats:italic>L<\/jats:italic><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>metrics.<\/jats:p><jats:p>Let us remark that our probabilistic analysis covers as special cases the uniform input model with<jats:italic>\u03d5<\/jats:italic>=1 and a smoothed analysis with Gaussian perturbations of standard deviation<jats:italic>\u03c3<\/jats:italic>with<jats:italic>\u03d5<\/jats:italic>\u223c1\/<jats:italic>\u03c3<\/jats:italic><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>.<\/jats:p>","DOI":"10.1007\/s00453-013-9801-4","type":"journal-article","created":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T15:49:15Z","timestamp":1371570555000},"page":"190-264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":100,"title":["Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP"],"prefix":"10.1007","volume":"68","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"issue":"5","key":"9801_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"9801_CR2","volume-title":"Handbook of Mathematics","author":"I.N. Bronshtein","year":"2007","unstructured":"Bronshtein, I.N., Semendyayev, K.A., Musiol, G., M\u00fchlig, H.: Handbook of Mathematics. Springer, Berlin (2007)"},{"issue":"6","key":"9801_CR3","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B. Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H.J., Tovey, C.A.: New results on the old k-Opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9801_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D.P. Dubhashi","year":"1998","unstructured":"Dubhashi, D.P., Ranjan, D.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99\u2013124 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"9801_CR5","first-page":"1295","volume-title":"Proc. of the 18th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M. Englert","year":"2007","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. In: Proc. of the 18th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1295\u20131304 (2007)"},{"key":"9801_CR6","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-60618-1_73","volume-title":"Proc. of the 21st Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"S. Fischer","year":"1995","unstructured":"Fischer, S., Torenvliet, L.: The malleability of TSP2opt. In: Proc. of the 21st Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 152\u2013166 (1995)"},{"key":"9801_CR7","volume-title":"Local Search in Combinatorial Optimization","author":"D.S. Johnson","year":"1997","unstructured":"Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study in local optimization. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. Wiley, New York (1997)"},{"issue":"2","key":"9801_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF01587089","volume":"44","author":"W. Kern","year":"1989","unstructured":"Kern, W.: A probabilistic analysis of the switching algorithm for the Euclidean TSP. Math. Program. 44(2), 213\u2013219 (1989)","journal-title":"Math. Program."},{"key":"9801_CR9","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1109\/SFCS.1989.63481","volume-title":"Proc. of the 30th Ann. IEEE Symp. on Foundations of Computer Science (FOCS)","author":"M.W. Krentel","year":"1989","unstructured":"Krentel, M.W.: Structure in locally optimal solutions. In: Proc. of the 30th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 216\u2013221 (1989)"},{"key":"9801_CR10","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Tight bounds for parallel randomized load balancing. Technical Report 324, Computer Engineering and Networks Laboratory, ETH, Zurich (2010)","DOI":"10.1145\/1993636.1993639"},{"key":"9801_CR11","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic for the traveling salesman problem. Oper. Res. 21, 489\u2013516 (1973)","journal-title":"Oper. Res."},{"key":"9801_CR12","unstructured":"Lueker, G.S.: Unpublished manuscript, Princeton University (1975)"},{"issue":"4","key":"9801_CR13","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9801_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"3","key":"9801_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9801_CR16","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0221030","volume":"21","author":"C.H. Papadimitriou","year":"1992","unstructured":"Papadimitriou, C.H.: The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21(3), 450\u2013465 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9801_CR17","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB\u2014a traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"issue":"3","key":"9801_CR18","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.J. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis\u00a0II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9801_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"9801_CR20","first-page":"87","volume-title":"Proc. of the 7th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"J. van Leeuwen","year":"1981","unstructured":"van Leeuwen, J., Schoon, A.A.: Untangling a traveling salesman tour in the plane. In: Proc. of the 7th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 87\u201398 (1981)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9801-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-013-9801-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9801-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9801-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T16:32:47Z","timestamp":1645806767000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-013-9801-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,19]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9801"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9801-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,19]]},"assertion":[{"value":"25 January 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}