{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:53:43Z","timestamp":1743054823022,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_39","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:05:04Z","timestamp":1246532704000},"page":"472-483","source":"Crossref","is-referenced-by-count":0,"title":["Smoothed Analysis of Balancing Networks"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In: 47th IEEE Symp. on Found. of Comp. Science (FOCS 2006), pp. 153\u2013164 (2006)","DOI":"10.1109\/FOCS.2006.79"},{"issue":"5","key":"39_CR2","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1145\/185675.185815","volume":"41","author":"J. Aspnes","year":"1994","unstructured":"Aspnes, J., Herlihy, M., Shavit, N.: Counting networks. J. of the ACM\u00a041(5), 1020\u20131048 (1994)","journal-title":"J. of the ACM"},{"key":"39_CR3","unstructured":"Bertsekas, D., Tsitsiklis, J.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific (1997)"},{"issue":"1","key":"39_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/rsa.10070","volume":"22","author":"T. Bohman","year":"2003","unstructured":"Bohman, T., Frieze, A., Martin, R.: How many random edges make a dense graph hamiltonian? Random Structures and Algorithms\u00a022(1), 33\u201342 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Feige, U., Frieze, A., Krivelevich, M., Vilenchik, D.: On smoothed k-CNF formulas and the walksat algorithm. In: 20th ACM-SIAM Symp. on Discrete Algorithms (SODA 2009) (2009)","DOI":"10.1137\/1.9781611973068.50"},{"issue":"4","key":"39_CR6","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1145\/76359.76362","volume":"36","author":"M. Dowd","year":"1989","unstructured":"Dowd, M., Perl, Y., Rudolph, L., Saks, M.: The periodic balanced sorting network. J. of the ACM\u00a036(4), 738\u2013757 (1989)","journal-title":"J. of the ACM"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U.: Refuting smoothed 3CNF formulas. In: 48th IEEE Symp. on Found. of Comp. Science (FOCS 2007), pp. 407\u2013417 (2007)","DOI":"10.1109\/FOCS.2007.16"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1002\/rsa.20172","volume":"30","author":"A. Flaxman","year":"2007","unstructured":"Flaxman, A., Frieze, A.: The diameter of randomly perturbed digraphs and some applications. Random Structures and Algorithms\u00a030, 484\u2013504 (2007)","journal-title":"Random Structures and Algorithms"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Sauerwald, T.: Near-perfect load balancing by randomized rounding. In: 41st Annual ACM Symposium on Theory of Computing, STOC 2009 (to appear, 2009)","DOI":"10.1145\/1536414.1536433"},{"key":"39_CR10","volume-title":"The Art of Multiprocessor Programming","author":"M. Herlihy","year":"2008","unstructured":"Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, San Francisco (2008)"},{"issue":"5","key":"39_CR11","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1016\/j.jpdc.2005.06.009","volume":"66","author":"M. Herlihy","year":"2006","unstructured":"Herlihy, M., Tirthapura, S.: Randomized smoothing networks. J. Parallel and Distributed Computing\u00a066(5), 626\u2013632 (2006a)","journal-title":"J. Parallel and Distributed Computing"},{"issue":"5","key":"39_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s00446-005-0130-y","volume":"18","author":"M. Herlihy","year":"2006","unstructured":"Herlihy, M., Tirthapura, S.: Self-stabilizing smoothing and counting networks. Distributed Computing\u00a018(5), 345\u2013357 (2006b)","journal-title":"Distributed Computing"},{"issue":"2","key":"39_CR13","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\u00a029(2), 180\u2013193 (2006)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"39_CR14","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., R\u00fcdiger, R.: Smoothed analysis of binary search trees. Theoret. Computer Sci.\u00a0378(3), 292\u2013315 (2007)","journal-title":"Theoret. Computer Sci."},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Sauerwald, T.: The impact of randomization in smoothing networks. In: 27th Annual ACM Principles of Distributed Computing (PODC 2008), pp. 345\u2013354 (2008)","DOI":"10.1145\/1400751.1400797"},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load balancing schemes. In: 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pp. 694\u2013705 (1998)","DOI":"10.1109\/SFCS.1998.743520"},{"issue":"1","key":"39_CR17","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. Program.\u00a0110(1), 21\u201356 (2007)","journal-title":"Math. Program."},{"issue":"3","key":"39_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D. Spielman","year":"2004","unstructured":"Spielman, D., Teng, S.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"J. of the ACM"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: Beyond hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. In: 47th IEEE Symp. on Found. of Comp. Science (FOCS 2006), pp. 133\u2013142 (2006)","DOI":"10.1109\/FOCS.2006.19"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02930-1_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T01:49:40Z","timestamp":1558403380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}