{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T00:06:32Z","timestamp":1758413192932,"version":"3.44.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T00:00:00Z","timestamp":1753056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T00:00:00Z","timestamp":1753056000000},"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,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, R\u00f6glin, and V\u00f6cking (<jats:italic>Algorithmica<\/jats:italic>, 2014) provided a smoothed analysis in the so-called one-step model in order to explain the performance of 2-opt on <jats:italic>d<\/jats:italic>-dimensional Euclidean instances, both in terms of running-time and in terms of approximation ratio. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation <jats:inline-formula>\n              <jats:tex-math>$$\\sigma $$<\/jats:tex-math>\n            <\/jats:inline-formula>, yields only weak bounds. We prove bounds that are polynomial in <jats:italic>n<\/jats:italic> and <jats:inline-formula>\n              <jats:tex-math>$$1\/\\sigma $$<\/jats:tex-math>\n            <\/jats:inline-formula> for the smoothed running-time with Gaussian perturbations. In addition, our analysis for Euclidean distances is much simpler than the existing smoothed analysis. Furthermore, we prove a smoothed approximation ratio of <jats:inline-formula>\n              <jats:tex-math>$$O(\\log (1\/\\sigma ))$$<\/jats:tex-math>\n            <\/jats:inline-formula>. This bound is almost tight, as we also provide a lower bound of <jats:inline-formula>\n              <jats:tex-math>$$\\Omega (\\frac{\\log n}{\\log \\log n})$$<\/jats:tex-math>\n            <\/jats:inline-formula> for <jats:inline-formula>\n              <jats:tex-math>$$\\sigma = O(1\/\\sqrt{n})$$<\/jats:tex-math>\n            <\/jats:inline-formula>. Our main technical novelty here is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and local optimum on all inputs (which only allows for a bound of <jats:inline-formula>\n              <jats:tex-math>$$O(1\/\\sigma )$$<\/jats:tex-math>\n            <\/jats:inline-formula>), but simultaneously bound them on the same input.<\/jats:p>","DOI":"10.1007\/s00453-025-01335-7","type":"journal-article","created":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T13:49:18Z","timestamp":1753105758000},"page":"1518-1563","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise"],"prefix":"10.1007","volume":"87","author":[{"given":"Marvin","family":"K\u00fcnnemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rianne","family":"Veenstra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,21]]},"reference":[{"key":"1335_CR1","unstructured":"Abramowitz, M., Stegun, I.\u00a0A.: editors. Pocketbook of mathematical functions. Harri Deutsch, (1984)"},{"issue":"5","key":"1335_CR2","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"},{"issue":"2","key":"1335_CR3","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s00453-012-9643-5","volume":"66","author":"M Bl\u00e4ser","year":"2013","unstructured":"Bl\u00e4ser, M., Manthey, B., Raghavendra Rao, B.V.: Smoothed analysis of partitioning algorithms for Euclidean functionals. Algorithmica 66(2), 397\u2013418 (2013)","journal-title":"Algorithmica"},{"key":"1335_CR4","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Engels, C., Manthey, B., Raghavendra Rao, B.\u00a0V.: Random shortest paths: Non-euclidean instances for metric optimization problems. In Krishnendu Chatterjee and Ji\u0159\u00ed Sgall, editors, Proc. of the 38th Int. Symp. on mathematical foundations of computer science (MFCS), volume 8087 of lecture notes in computer science, pages 219\u2013230. Springer, (2013)","DOI":"10.1007\/978-3-642-40313-2_21"},{"issue":"4","key":"1335_CR5","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1137\/21M146199X","volume":"52","author":"UA Brodowsky","year":"2023","unstructured":"Brodowsky, U.A., Hougardy, S., Zhong, X.: The approximation ratio of the k-opt heuristic for the Euclidean traveling salesman problem. SIAM J. Comput. 52(4), 841\u2013864 (2023)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"1335_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10107-013-0683-7","volume":"146","author":"T Brunsch","year":"2014","unstructured":"Brunsch, T., R\u00f6glin, H., Rutten, C., Vredeveld, T.: Smoothed performance guarantees for local search. Math. Program. 146(1\u20132), 185\u2013218 (2014)","journal-title":"Math. Program."},{"issue":"6","key":"1335_CR7","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 [CDATA[k]]$$k$$-opt algorithm for the traveling salesman problem. SIAM J. Comput. 28(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1335_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-015-0043-5","volume":"73","author":"R Curticapean","year":"2015","unstructured":"Curticapean, R., K\u00fcnnemann, M.: A quantization framework for smoothed analysis of Euclidean optimization problems. Algorithmica 73(3), 1\u201328 (2015)","journal-title":"Algorithmica"},{"key":"1335_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"1335_CR10","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"2013","unstructured":"Durrett, R.: Probability: Theory and Examples. Cambridge University Press, Cambridge (2013)"},{"issue":"2","key":"1335_CR11","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)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1335_CR12","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)","journal-title":"Algorithmica"},{"key":"1335_CR13","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.dam.2014.05.041","volume":"195","author":"M Etscheid","year":"2015","unstructured":"Etscheid, M.: Performance guarantees for scheduling algorithms under perturbed machine speeds. Discret. Appl. Math. 195, 84\u2013100 (2015)","journal-title":"Discret. Appl. Math."},{"key":"1335_CR14","volume-title":"Statistical Distributions","author":"M Evans","year":"2000","unstructured":"Evans, M., Hastings, N., Peacock, B.: Statistical Distributions, 3rd edn. Wiley, Hoboken (2000)","edition":"3"},{"issue":"6","key":"1335_CR15","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1016\/j.adhoc.2010.08.016","volume":"9","author":"S Funke","year":"2011","unstructured":"Funke, S., Laue, S., Lotker, Z., Naujoks, R.: Power assignment problems in wireless communication: Covering points by disks, reaching few receivers quickly, and energy-efficient travelling salesman tours. Ad Hoc Netw. 9(6), 1028\u20131035 (2011)","journal-title":"Ad Hoc Netw."},{"key":"1335_CR16","volume-title":"Local Search in Combinatorial Optimization","author":"DS Johnson","year":"1997","unstructured":"Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. Wiley, Hoboken (1997)"},{"key":"1335_CR17","volume-title":"The Traveling Salesman Problem and its Variations","author":"DS Johnson","year":"2002","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"1335_CR18","unstructured":"Karger, D., Onak, K.: Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. In Proc. of the 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1207\u20131216. SIAM, (2007)"},{"issue":"2","key":"1335_CR19","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 TSP. Math. Program. 44(2), 213\u2013219 (1989)","journal-title":"Math. Program."},{"key":"1335_CR20","doi-asserted-by":"crossref","unstructured":"K\u00fcnnemann, M., Manthey, B.: Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In Magn\u00fas\u00a0M. Halld\u00f3rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, In: Proc. of the 42nd Int. Coll. on Automata, Languages and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 859\u2013871. Springer, (2015)","DOI":"10.1007\/978-3-662-47672-7_70"},{"key":"1335_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1017\/9781108637435.018","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"B Manthey","year":"2020","unstructured":"Manthey, B.: Smoothed analysis of local search. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 285\u2013308. Cambridge University Press, Cambridge (2020)"},{"issue":"6","key":"1335_CR22","first-page":"280","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)","journal-title":"IT Inf Technol"},{"key":"1335_CR23","unstructured":"Manthey, B.,Rhijn, J.V.: Improved smoothed analysis of 2-opt for the Euclidean TSP. In Satoru Iwata and Naonori Kakimura, editors, In: Proc. 34th Int. Symposium on Algorithms and Computation (ISAAC), volume 283 of LIPIcs, pages 52:1\u201352:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2023)"},{"key":"1335_CR24","doi-asserted-by":"crossref","unstructured":"Manthey, B.,Veenstra, R.: Smoothed analysis of the 2-Opt heuristic for the TSP: Polynomial bounds for Gaussian noise. In Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam, editors, In: Proc. of the 24th Ann. Int. Symp. on Algorithms and Computation (ISAAC), volume 8283 of Lecture Notes in Computer Science, pages 579\u2013589. Springer, (2013)","DOI":"10.1007\/978-3-642-45030-3_54"},{"issue":"4","key":"1335_CR25","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for Geometric TSP, $$k$$[CDATA[k]]-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1335_CR26","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 traveling salesman problem is NP-complete. Theoret. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1335_CR27","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M., II.: 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":"1335_CR28","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)","journal-title":"J. ACM"},{"issue":"10","key":"1335_CR29","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)","journal-title":"Commun. ACM"},{"key":"1335_CR30","unstructured":"Nijnatten, F.v., Sitters, R., Woeginger, G.\u00a0J., Wolff, A., de\u00a0Berg, M.: The traveling salesman problem under squared Euclidean distances. In Jean-Yves Marion and Thomas Schwentick, editors, In: Proc. of the 27th Int. Symp. on Theoretical Aspects of Computer Science (STACS), volume\u00a05 of LIPIcs, pages 239\u2013250. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, (2010)"},{"key":"1335_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093472","volume-title":"Probability theory of classical Euclidean optimization problems","author":"JE Yukich","year":"1998","unstructured":"Yukich, J.E.: Probability theory of classical Euclidean optimization problems. Springer, Berlin (1998)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01335-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01335-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01335-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:14:05Z","timestamp":1758399245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01335-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,21]]},"references-count":31,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1335"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01335-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,7,21]]},"assertion":[{"value":"26 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}