{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:26:07Z","timestamp":1758475567665,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_70","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"859-871","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic"],"prefix":"10.1007","author":[{"given":"Marvin","family":"K\u00fcnnemann","sequence":"first","affiliation":[]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"5","key":"70_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 45(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"70_CR2","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the $$k$$-means method. Journal of the ACM 58(5) (2011)","DOI":"10.1145\/2027216.2027217"},{"issue":"2","key":"70_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 J. Comp. 39(2), 766\u2013782 (2009)","journal-title":"SIAM J. Comp."},{"issue":"2","key":"70_CR4","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., Rao, B.V.R.: Smoothed analysis of partitioning algorithms for Euclidean functionals. Algorithmica 66(2), 397\u2013418 (2013)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"70_CR5","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. Mathematical Programming 146(1\u20132), 185\u2013218 (2014)","journal-title":"Mathematical Programming"},{"issue":"6","key":"70_CR6","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. Comp. 28(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comp."},{"key":"70_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-642-40450-4_30","volume-title":"Algorithms \u2013 ESA 2013","author":"R Curticapean","year":"2013","unstructured":"Curticapean, R., K\u00fcnnemann, M.: A quantization framework for smoothed analysis of euclidean optimization problems. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 349\u2013360. Springer, Heidelberg (2013)"},{"issue":"1","key":"70_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)","journal-title":"Algorithmica"},{"key":"70_CR9","unstructured":"Etscheid, M.: Performance guarantees for scheduling algorithms under perturbed machine speeds. Discrete Applied Mathematics (to appear)"},{"key":"70_CR10","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, chap. 8. John Wiley & Sons (1997)"},{"key":"70_CR11","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, chap. 9. Kluwer Academic Publishers (2002)"},{"key":"70_CR12","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), pp. 1207\u20131216. SIAM (2007)"},{"key":"70_CR13","doi-asserted-by":"crossref","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: Analysis of algorithms beyond worst case. It - Information Technology 53(6), 280\u2013286 (2011)","DOI":"10.1524\/itit.2011.0654"},{"issue":"1","key":"70_CR14","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. J. of Comp. Geom. 4(1), 94\u2013132 (2013)","journal-title":"J. of Comp. Geom."},{"key":"70_CR15","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.) ISAAC 2013. LNCS, vol. 8283, pp. 579\u2013589. Springer, Heidelberg (2013)"},{"issue":"4","key":"70_CR16","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$$-MST, and related problems. SIAM J. Comp. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"70_CR17","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. Theoretical Computer Science 4(3), 237\u2013244 (1977)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"70_CR18","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 II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comp. 6(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"70_CR19","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. Journal of the ACM 51(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"10","key":"70_CR20","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. Communications of the ACM 52(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"},{"key":"70_CR21","doi-asserted-by":"crossref","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol. 1675. Springer (1998)","DOI":"10.1007\/BFb0093472"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_70","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T13:27:07Z","timestamp":1674566827000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}