{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:43:05Z","timestamp":1725698585962},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_20","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"198-209","source":"Crossref","is-referenced-by-count":1,"title":["Smoothed Complexity Theory"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. J. ACM\u00a058(5) (2011)","DOI":"10.1145\/2027216.2027217"},{"issue":"3","key":"20_CR2","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. J. Comput. System Sci.\u00a069(3), 306\u2013329 (2004)","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"20_CR3","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 J. Comput.\u00a035(4), 855\u2013881 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. J. Comput. System Sci.\u00a044(2), 193\u2013219 (1992)","journal-title":"J. Comput. System Sci."},{"key":"20_CR5","unstructured":"Bl\u00e4ser, M., Manthey, B., Rao, B.V.R.: Smoothed analysis of partitioning algorithms for Euclidean functionals. Algorithmica (to appear)"},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"A.L. Blum","year":"1995","unstructured":"Blum, A.L., Spencer, J.: Coloring random and semi-random k-colorable graphs. J. Algorithms\u00a019(2), 204\u2013234 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000004","volume":"2","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Foundations and Trends in Theoret. Comput. Sci.\u00a02(1), 1\u2013106 (2006)","journal-title":"Foundations and Trends in Theoret. Comput. Sci."},{"issue":"2","key":"20_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1002\/rsa.10112","volume":"24","author":"T. Bohman","year":"2004","unstructured":"Bohman, T., Frieze, A.M., Krivelevich, M., Martin, R.: Adding random edges to dense graphs. Random Struct. Algorithms\u00a024(2), 105\u2013117 (2004)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"20_CR9","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0963548306007917","volume":"16","author":"A. Coja-Oghlan","year":"2007","unstructured":"Coja-Oghlan, A.: Colouring semirandom graphs. Combin. Probab. Comput.\u00a016(4), 515\u2013552 (2007)","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jalgor.2004.07.003","volume":"62","author":"A. Coja-Oghlan","year":"2007","unstructured":"Coja-Oghlan, A.: Solving NP-hard semirandom graph problems in polynomial expected time. J. Algorithms\u00a062(1), 19\u201346 (2007)","journal-title":"J. Algorithms"},{"key":"20_CR11","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. 20th Ann. Symp. on Discrete Algorithms (SODA), pp. 451\u2013460. SIAM (2009)","DOI":"10.1137\/1.9781611973068.50"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Damerow, V., Manthey, B., Meyer auf der Heide, F., R\u00e4cke, H., Scheideler, C., Sohler, C., Tantau, T.: Smoothed analysis of left-to-right maxima with applications. ACM Trans. Algorithms 8(3), article 30","DOI":"10.1145\/2229163.2229174"},{"key":"20_CR13","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. In: Proc. 18th Ann. Symp. on Discrete Algorithms (SODA), pp. 1295\u20131304. SIAM (2007)"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U.: Refuting smoothed 3CNF formulas. In: Proc. 48th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 407\u2013417. IEEE (2007)","DOI":"10.1109\/FOCS.2007.16"},{"issue":"4","key":"20_CR15","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kilian, J.: Heuristics for semirandom graph problems. J. Comput. System Sci.\u00a063(4), 639\u2013671 (2001)","journal-title":"J. Comput. System Sci."},{"issue":"3-4","key":"20_CR16","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\u00a062(3-4), 879\u2013905 (2012)","journal-title":"Algorithmica"},{"key":"20_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company (1979)"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich, Y.: Average case completeness. J. Comput. System Sci.\u00a042(3), 346\u2013398 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"20_CR19","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 Struct. Algorithms\u00a029(2), 180\u2013193 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"20_CR20","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"Levin, L.A.: Average case complete problems. SIAM J. Comput.\u00a015(1), 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: Average case complexity under the universal distribution equals worst-case complexity. Inform. Process. Lett.\u00a042(3), 145\u2013149 (1992)","journal-title":"Inform. Process. Lett."},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: Analysis of algorithms beyond worst case. it \u2013 Information Technology\u00a053(6) (2011)","DOI":"10.1524\/itit.2011.0654"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Moitra, A., O\u2019Donnell, R.: Pareto optimal solutions for smoothed analysts. In: Proc. 43rd Ann. Symp. on Theory of Computing (STOC), pp. 225\u2013234. ACM (2011)","DOI":"10.1145\/1993636.1993667"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"R\u00f6glin, H., Teng, S.-H.: Smoothed analysis of multiobjective optimization. In: Proc. 50th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 681\u2013690. IEEE (2009)","DOI":"10.1109\/FOCS.2009.21"},{"issue":"1","key":"20_CR25","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. Math. Prog.\u00a0110(1), 21\u201356 (2007)","journal-title":"Math. Prog."},{"issue":"1-2","key":"20_CR26","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10107-003-0448-9","volume":"97","author":"D.A. Spielman","year":"2003","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of termination of linear programming algorithms. Math. Prog.\u00a097(1-2), 375\u2013404 (2003)","journal-title":"Math. Prog."},{"issue":"3","key":"20_CR27","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. J. ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"20_CR28","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. Commun. ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"2","key":"20_CR29","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 J. Comput.\u00a039(2), 646\u2013678 (2009)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:08:01Z","timestamp":1620130081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}