{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T02:07:44Z","timestamp":1774922864005,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642450297","type":"print"},{"value":"9783642450303","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_54","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"579-589","source":"Crossref","is-referenced-by-count":10,"title":["Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rianne","family":"Veenstra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"54_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. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. Journal of the ACM\u00a058(5) (2011)","DOI":"10.1145\/2027216.2027217"},{"issue":"2","key":"54_CR3","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/070683921","volume":"39","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. SIAM Journal on Computing\u00a039(2), 766\u2013782 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-40313-2_21","volume-title":"Mathematical Foundations of Computer Science 2013","author":"K. Bringmann","year":"2013","unstructured":"Bringmann, K., Engels, C., Manthey, B., Rao, B.V.R.: Random shortest paths: Non-euclidean instances for metric optimization problems. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 219\u2013230. Springer, Heidelberg (2013)"},{"issue":"6","key":"54_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 Journal on Computing\u00a028(6), 1998\u20132029 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"54_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. Operations Research Letters\u00a037(2), 83\u201384 (2009)","journal-title":"Operations Research Letters"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica (to appear)","DOI":"10.1007\/s00453-013-9801-4"},{"issue":"6","key":"54_CR8","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 Networks\u00a09(6), 1028\u20131035 (2011)","journal-title":"Ad Hoc Networks"},{"key":"54_CR9","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, ch.\u00a08. John Wiley & Sons (1997)"},{"key":"54_CR10","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, ch.\u00a09. Kluwer Academic Publishers (2002)"},{"issue":"2","key":"54_CR11","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. Mathematical Programming\u00a044(2), 213\u2013219 (1989)","journal-title":"Mathematical Programming"},{"issue":"6","key":"54_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 \u2013 Information Technology\u00a053(6), 280\u2013286 (2011)","journal-title":"it \u2013 Information Technology"},{"issue":"1","key":"54_CR13","first-page":"94","volume":"4","author":"B. Manthey","year":"2013","unstructured":"Manthey, B., R\u00f6glin, H.: Worst-case and smoothed analysis of k-means clustering with Bregman divergences. Journal of Computational Geometry\u00a04(1), 94\u2013132 (2013)","journal-title":"Journal of Computational Geometry"},{"issue":"4","key":"54_CR14","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 Journal on Computing\u00a028(4), 1298\u20131309 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR15","unstructured":"van Nijnatten, F., Sitters, R., Woeginger, G.J., Wolff, A., de Berg, M.: The traveling salesman problem under squared Euclidean distances. In: Proc. of the 27th Int. Symp. on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol.\u00a05, pp. 239\u2013250. Schloss Dagstuhl (2010)"},{"issue":"3","key":"54_CR16","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. Theoretical Computer Science\u00a04(3), 237\u2013244 (1977)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"54_CR17","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. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"10","key":"54_CR18","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Communications of the ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol.\u00a01675. Springer (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T03:51:20Z","timestamp":1548820280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}