{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T19:10:02Z","timestamp":1748545802773,"version":"3.41.0"},"publisher-location":"Cham","reference-count":59,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"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-319-21840-3_43","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"518-527","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Smoothed Analysis of Local Search Algorithms"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R.: The smoothed complexity of edit distance. ACM Transactions on Algorithms 8(4), 44:1\u201344:25 (2012)","DOI":"10.1145\/2344422.2344434"},{"key":"43_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":"43_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 39(2), 766\u2013782 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"43_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-540-45138-9_14","volume-title":"Mathematical Foundations of Computer Science 2003","author":"C Banderier","year":"2003","unstructured":"Banderier, C., Beier, R., Mehlhorn, K.: Smoothed analysis of three combinatorial problems. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 198\u2013207. Springer, Heidelberg (2003)"},{"issue":"1","key":"43_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average case and smoothed competitive analysis of the multilevel feedback algorithm. Mathematics of Operations Research 31(1), 85\u2013108 (2006)","journal-title":"Mathematics of Operations Research"},{"key":"43_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-72792-7_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Beier","year":"2007","unstructured":"Beier, R., R\u00f6glin, H., V\u00f6cking, B.: The smoothed number of pareto optimal solutions in bicriteria integer optimization. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 53\u201367. Springer, Heidelberg (2007)"},{"issue":"3","key":"43_CR7","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R Beier","year":"2004","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. Journal of Computer and System Sciences 69(3), 306\u2013329 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"43_CR8","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and losers in discrete optimization. SIAM Journal on Computing 35(4), 855\u2013881 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"43_CR9","first-page":"57","volume":"1","author":"M de Berg","year":"2010","unstructured":"de Berg, M., Haverkort, H.J., Tsirogiannis, C.P.: Visibility maps of realistic terrains have linear smoothed complexity. Journal of Computational Geometry 1(1), 57\u201371 (2010)","journal-title":"Journal of Computational Geometry"},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.dam.2014.11.025","volume":"185","author":"A Berger","year":"2015","unstructured":"Berger, A., R\u00f6glin, H., van der Zwaan, R.: Internet routing between autonomous systems: Fast algorithms for path trading. Discrete Applied Mathematics 185, 8\u201317 (2015)","journal-title":"Discrete Applied Mathematics"},{"key":"43_CR11","unstructured":"Bl\u00e4ser, M., Manthey, B.: Smoothed complexity theory. ACM Transactions on Computation Theory (to appear)"},{"issue":"2","key":"43_CR12","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"},{"key":"43_CR13","unstructured":"Blum, A.L., Dunagan, J.D.: Smoothed analysis of the perceptron algorithm for linear programming. In: Proc. of the 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 905\u2013914. SIAM (2002)"},{"issue":"6","key":"43_CR14","doi-asserted-by":"publisher","first-page":"647","DOI":"10.7155\/jgaa.00310","volume":"17","author":"T Brunsch","year":"2013","unstructured":"Brunsch, T., Cornelissen, K., Manthey, B., R\u00f6glin, H.: Smoothed analysis of belief propagation for minimum-cost flow and matching. Journal of Graph Algorithms and Applications 17(6), 647\u2013670 (2013)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"43_CR15","doi-asserted-by":"crossref","unstructured":"Brunsch, T., Cornelissen, K., Manthey, B., R\u00f6glin, H., R\u00f6sner, C.: Smoothed analysis of the successive shortest path algorithm. Computing Research Repository 1501.05493 [cs.DS], arXiv (2015), a preliminary version has been presented at SODA (2013)","DOI":"10.1137\/1.9781611973105.85"},{"issue":"10","key":"43_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.4086\/toc.2014.v010a010","volume":"10","author":"T Brunsch","year":"2014","unstructured":"Brunsch, T., Goyal, N., Rademacher, L., R\u00f6glin, H.: Lower bounds for the average and smoothed number of pareto-optima. Theory of Computing 10(10), 237\u2013256 (2014)","journal-title":"Theory of Computing"},{"issue":"1","key":"43_CR17","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2699445","volume":"62","author":"T Brunsch","year":"2015","unstructured":"Brunsch, T., R\u00f6glin, H.: Improved smoothed analysis of multiobjective optimization. Journal of the ACM 62(1), 4 (2015)","journal-title":"Journal of the ACM"},{"issue":"1\u20132","key":"43_CR18","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":"4","key":"43_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.matpur.2006.06.001","volume":"86","author":"P B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F., Lotz, M.: Smoothed analysis of complex conic condition numbers. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es 86(4), 293\u2013309 (2006)","journal-title":"Journal de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"issue":"263","key":"43_CR20","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1090\/S0025-5718-08-02060-7","volume":"77","author":"P B\u00fcrgisser","year":"2008","unstructured":"B\u00fcrgisser, P., Cucker, F., Lotz, M.: The probability that a slightly perturbed numerical analysis problem is difficult. Mathematics of Computation 77(263), 1559\u20131583 (2008)","journal-title":"Mathematics of Computation"},{"issue":"6","key":"43_CR21","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 28(6), 1998\u20132029 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"43_CR22","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.comgeo.2008.10.005","volume":"42","author":"S Chaudhuri","year":"2009","unstructured":"Chaudhuri, S., Koltun, V.: Smoothed analysis of probabilistic roadmaps. Computational Geometry 42(8), 731\u2013747 (2009)","journal-title":"Computational Geometry"},{"key":"43_CR23","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Feige, U., Frieze, A.M., Krivelevich, M., Vilenchik, D.: On smoothed $$k$$-CNF formulas and the Walksat algorithm. In: Proc. of the 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 451\u2013460. SIAM (2009)","DOI":"10.1137\/1.9781611973068.50"},{"key":"43_CR25","doi-asserted-by":"crossref","unstructured":"Cornelissen, K., Manthey, B.: Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm. In: Proc. of the 21st Ann. Int. Computing and Combinatorics Conf. (COCOON). LNCS. Springer (to appear, 2015)","DOI":"10.1007\/978-3-319-21398-9_55"},{"key":"43_CR26","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)"},{"key":"43_CR27","doi-asserted-by":"crossref","unstructured":"Damerow, V., Manthey, B., Auf der Heide, F.M., R\u00e4cke, H., Scheideler, C., Sohler, C., Tantau, T.: Smoothed analysis of left-to-right maxima with applications. ACM Transactions on Algorithms 8(3) (2012)","DOI":"10.1145\/2229163.2229174"},{"key":"43_CR28","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Spielman, D.A.: Improved smoothed analysis of the shadow vertex simplex method. In: Proc. of the 46th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 349\u2013356. IEEE Computer Society (2005)","DOI":"10.1109\/SFCS.2005.44"},{"issue":"2","key":"43_CR29","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10107-009-0278-5","volume":"126","author":"J Dunagan","year":"2011","unstructured":"Dunagan, J., Spielman, D.A., Teng, S.H.: Smoothed analysis of condition numbers and complexity implications for linear programming. Mathematical Programming 126(2), 315\u2013350 (2011)","journal-title":"Mathematical Programming"},{"key":"43_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-22006-7_15","volume-title":"Automata, Languages and Programming","author":"R Els\u00e4sser","year":"2011","unstructured":"Els\u00e4sser, R., Tscheuschner, T.: Settling the complexity of local max-cut (almost) completely. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 171\u2013182. Springer, Heidelberg (2011)"},{"issue":"1","key":"43_CR31","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":"43_CR32","unstructured":"Etscheid, M.: Performance guarantees for scheduling algorithms under perturbed machine speeds. Discrete Applied Mathematics (to appear)"},{"key":"43_CR33","doi-asserted-by":"crossref","unstructured":"Etscheid, M., R\u00f6glin, H.: Smoothed analysis of local search for the maximum-cut problem. In: Proc. of the 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 882\u2013889. SIAM (2014)","DOI":"10.1137\/1.9781611973402.66"},{"key":"43_CR34","doi-asserted-by":"crossref","unstructured":"Feige, U.: Refuting smoothed 3CNF formulas. In: Proc. of the 48th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 407\u2013417. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.16"},{"issue":"4","key":"43_CR35","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1002\/rsa.20172","volume":"30","author":"AD Flaxman","year":"2007","unstructured":"Flaxman, A.D., Frieze, A.M.: The diameter of randomly perturbed digraphs and some applications. Random Structures and Algorithms 30(4), 484\u2013504 (2007)","journal-title":"Random Structures and Algorithms"},{"issue":"3\u20134","key":"43_CR36","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s00453-011-9490-9","volume":"62","author":"M Fouz","year":"2012","unstructured":"Fouz, M., Kufleitner, M., Manthey, B., Zeini Jahromi, N.: On smoothed analysis of quicksort and Hoare\u2019s find. Algorithmica 62(3\u20134), 879\u2013905 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"43_CR37","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/rsa.20341","volume":"39","author":"T Friedrich","year":"2011","unstructured":"Friedrich, T., Sauerwald, T., Vilenchik, D.: Smoothed analysis of balancing networks. Random Structures and Algorithms 39(1), 115\u2013138 (2011)","journal-title":"Random Structures and Algorithms"},{"key":"43_CR38","doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Samorodnitsky, A., Teng, S.H.: Learning and smoothed analysis. In: Proc. of the 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 395\u2013404. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.60"},{"key":"43_CR39","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":"43_CR40","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Nikolova, E.: On the hardness and smoothed complexity of quasi-concave minimization. In: Proc. of the 48th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 472\u2013482 (2007)","DOI":"10.1109\/FOCS.2007.68"},{"issue":"2","key":"43_CR41","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1002\/rsa.20097","volume":"29","author":"M Krivelevich","year":"2006","unstructured":"Krivelevich, M., Sudakov, B., Tetali, P.: On smoothed analysis in dense graphs and formulas. Random Structures and Algorithms 29(2), 180\u2013193 (2006)","journal-title":"Random Structures and Algorithms"},{"key":"43_CR42","doi-asserted-by":"crossref","unstructured":"K\u00fcnnemann, M., Manthey, B.: Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In: Proc. of the 42nd Int. Coll. on Automata, Languages and Programming (ICALP). LNCS. Springer (to appear, 2015)","DOI":"10.1007\/978-3-662-47672-7_70"},{"issue":"2","key":"43_CR43","doi-asserted-by":"publisher","first-page":"498","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. Operations Research 21(2), 498\u2013516 (1973)","journal-title":"Operations Research"},{"issue":"12","key":"43_CR44","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1016\/j.dam.2012.06.008","volume":"161","author":"B Manthey","year":"2013","unstructured":"Manthey, B., Plociennik, K.: Approximating independent set in perturbed graphs. Discrete Applied Mathematics 161(12), 1761\u20131768 (2013)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"43_CR45","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/j.tcs.2007.02.035","volume":"378","author":"B Manthey","year":"2007","unstructured":"Manthey, B., Reischuk, R.: Smoothed analysis of binary search trees. Theoretical Computer Science 378(3), 292\u2013315 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"43_CR46","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 - Information Technology 53(6), 280\u2013286 (2011)","journal-title":"it - Information Technology"},{"issue":"1","key":"43_CR47","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 4(1), 94\u2013132 (2013)","journal-title":"Journal of Computational Geometry"},{"key":"43_CR48","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":"5","key":"43_CR49","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1137\/110851833","volume":"41","author":"A Moitra","year":"2012","unstructured":"Moitra, A., O\u2019Donnell, R.: Pareto optimal solutions for smoothed analysts. SIAM Journal on Computing 41(5), 1266\u20131284 (2012)","journal-title":"SIAM Journal on Computing"},{"key":"43_CR50","doi-asserted-by":"crossref","unstructured":"R\u00f6glin, H., Teng, S.H.: Smoothed analysis of multiobjective optimization. In: Proc. of the 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 681\u2013690. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.21"},{"issue":"1","key":"43_CR51","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H R\u00f6glin","year":"2007","unstructured":"R\u00f6glin, H., V\u00f6cking, B.: Smoothed analysis of integer programming. Mathematical Programming 110(1), 21\u201356 (2007)","journal-title":"Mathematical Programming"},{"issue":"2","key":"43_CR52","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1137\/S0895479803436202","volume":"28","author":"A Sankar","year":"2006","unstructured":"Sankar, A., Spielman, D.A., Teng, S.H.: Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications 28(2), 446\u2013476 (2006)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"1\u20133","key":"43_CR53","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.tcs.2005.04.006","volume":"241","author":"G Sch\u00e4fer","year":"2005","unstructured":"Sch\u00e4fer, G., Sivadasan, N.: Topology matters: Smoothed competitiveness of metrical task systems. Theoretical Computer Science 241(1\u20133), 216\u2013246 (2005)","journal-title":"Theoretical Computer Science"},{"key":"43_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-540-45078-8_23","volume-title":"Algorithms and Data Structures","author":"DA Spielman","year":"2003","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 256\u2013270. Springer, Heidelberg (2003)"},{"issue":"1\u20132","key":"43_CR55","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10107-003-0448-9","volume":"97","author":"DA Spielman","year":"2003","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, Series B 97(1\u20132), 375\u2013404 (2003)","journal-title":"Mathematical Programming, Series B"},{"issue":"3","key":"43_CR56","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":"43_CR57","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"},{"issue":"272","key":"43_CR58","doi-asserted-by":"publisher","first-page":"2333","DOI":"10.1090\/S0025-5718-2010-02396-8","volume":"79","author":"T Tao","year":"2010","unstructured":"Tao, T., Vu, V.H.: Smooth analysis of the condition number and the least singular value. Mathematics of Computation 79(272), 2333\u20132352 (2010)","journal-title":"Mathematics of Computation"},{"issue":"2","key":"43_CR59","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1137\/070683386","volume":"39","author":"R Vershynin","year":"2009","unstructured":"Vershynin, R.: Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. SIAM Journal on Computing 39(2), 646\u2013678 (2009)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T18:50:29Z","timestamp":1748544629000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":59,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_43","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":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}