{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T02:06:18Z","timestamp":1774922778044,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T00:00:00Z","timestamp":1744243200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T00:00:00Z","timestamp":1744243200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.KLEIN.176"],"award-info":[{"award-number":["OCENW.KLEIN.176"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile this difference between practice and theory have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey and Veenstra, who obtained smoothed complexity bounds polynomial in <jats:italic>n<\/jats:italic>, the dimension <jats:italic>d<\/jats:italic>, and the perturbation strength <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sigma ^{-1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>\u03c3<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. However, their analysis only works for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$d \\ge 4$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. The only previous analysis for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$d \\le 3$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> was performed by Englert, R\u00f6glin and V\u00f6cking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in <jats:italic>n<\/jats:italic> and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sigma ^{-d}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>\u03c3<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mi>d<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, and super-exponential in <jats:italic>d<\/jats:italic>. As the fact that no direct analysis exists for Gaussian perturbations that yields polynomial bounds for all <jats:italic>d<\/jats:italic> is somewhat unsatisfactory, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt with Gaussian perturbations.<\/jats:p>","DOI":"10.1007\/s00453-025-01309-9","type":"journal-article","created":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:12:03Z","timestamp":1744258323000},"page":"1008-1039","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Smoothed Analysis of 2-Opt for the Euclidean TSP"],"prefix":"10.1007","volume":"87","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesse","family":"van Rhijn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,10]]},"reference":[{"key":"1309_CR1","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctv346t9c","volume-title":"Local Search in Combinatorial Optimization","year":"2003","unstructured":"Aarts, E., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. Princeton University Press, Princeton (2003). https:\/\/doi.org\/10.2307\/j.ctv346t9c"},{"key":"1309_CR2","volume-title":"Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables","author":"M Abramowitz","year":"1974","unstructured":"Abramowitz, M.: Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables. Dover Publications Inc, Mineola (1974)"},{"issue":"125","key":"1309_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1090\/S0025-5718-1974-0333287-7","volume":"28","author":"DE Amos","year":"1974","unstructured":"Amos, D.E.: Computation of modified Bessel functions and their ratios. Math. Comput. 28(125), 239\u2013251 (1974). https:\/\/doi.org\/10.1090\/S0025-5718-1974-0333287-7","journal-title":"Math. Comput."},{"issue":"5","key":"1309_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.2307\/2589145","volume":"106","author":"TM Apostol","year":"1999","unstructured":"Apostol, T.M.: An elementary view of Euler\u2019s summation formula. Am. Math. Mon. 106(5), 409\u2013418 (1999). https:\/\/doi.org\/10.2307\/2589145","journal-title":"Am. Math. Mon."},{"issue":"6","key":"1309_CR5","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H., Tovey, C.: New results on the old k-opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6), 1998\u20132029 (1999). https:\/\/doi.org\/10.1137\/S0097539793251244","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1309_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.orl.2008.12.002","volume":"37","author":"C Engels","year":"2009","unstructured":"Engels, C., Manthey, B.: Average-case approximation ratio of the 2-opt algorithm for the TSP. Oper. Res. Lett. 37(2), 83\u201384 (2009). https:\/\/doi.org\/10.1016\/j.orl.2008.12.002","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1309_CR7","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/2972953","volume":"13","author":"M Englert","year":"2016","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Smoothed analysis of the 2-opt algorithm for the general TSP. ACM Trans. Algorithms 13(1), 10:1-10:15 (2016). https:\/\/doi.org\/10.1145\/2972953","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1309_CR8","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s00453-013-9801-4","volume":"68","author":"M Englert","year":"2014","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica 68(1), 190\u2013264 (2014). https:\/\/doi.org\/10.1007\/s00453-013-9801-4. arXiv:2302.06889","journal-title":"Algorithmica"},{"key":"1309_CR9","volume-title":"Continuous Univariate Distributions","author":"NL Johnson","year":"1995","unstructured":"Johnson, N.L., Kotz, S., Balakrishnan, N.: Continuous Univariate Distributions, vol. 2. Wiley, New York (1995)"},{"key":"1309_CR10","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21708-5","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2000","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics, Springer, Berlin (2000). https:\/\/doi.org\/10.1007\/978-3-662-21708-5"},{"key":"1309_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1017\/9781108637435.018","volume-title":"Beyond the Worst-Case Analysis of Algorithm","author":"B Manthey","year":"2021","unstructured":"Manthey, B.: Smoothed analysis of local search. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithm, pp. 285\u2013308. Cambridge University Press, Cambridge (2021). https:\/\/doi.org\/10.1017\/9781108637435.018"},{"issue":"6","key":"1309_CR12","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1524\/itit.2011.0654","volume":"53","author":"B Manthey","year":"2011","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: analysis of algorithms beyond worst case. IT-Inf. Technol. 53(6), 280\u2013286 (2011). https:\/\/doi.org\/10.1524\/itit.2011.0654","journal-title":"IT-Inf. Technol."},{"key":"1309_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-642-45030-3_54","volume-title":"Algorithms and Computation","author":"B Manthey","year":"2013","unstructured":"Manthey, B., Veenstra, R.: Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, pp. 579\u2013589. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-642-45030-3_54 . arXiv:2308.00306"},{"issue":"3","key":"1309_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977). https:\/\/doi.org\/10.1016\/0304-3975(77)90012-3","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1309_CR15","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA 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). https:\/\/doi.org\/10.1145\/990308.990310","journal-title":"J. ACM"},{"issue":"10","key":"1309_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009). https:\/\/doi.org\/10.1145\/1562764.1562785","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01309-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01309-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01309-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T21:02:58Z","timestamp":1754686978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01309-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,10]]},"references-count":16,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1309"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01309-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,10]]},"assertion":[{"value":"13 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}