{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:24:00Z","timestamp":1725600240074},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642222993"},{"type":"electronic","value":"9783642223006"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_10","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T08:41:31Z","timestamp":1312879291000},"page":"110-121","source":"Crossref","is-referenced-by-count":4,"title":["Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals"],"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"}]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","volume-title":"Network Flows","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.4064\/am28-2-5","volume":"28","author":"B. Anthes","year":"2001","unstructured":"Anthes, B., R\u00fcschendorf, L.: On the weighted Euclidean matching problem in R\n                \n                  d\n                 dimensions. Applicationes Mathematicae\u00a028(2), 181\u2013190 (2001)","journal-title":"Applicationes Mathematicae"},{"key":"10_CR3","first-page":"405","volume-title":"Proc. 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS)","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. In: Proc. 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 405\u2013414. IEEE, Los Alamitos (2009)"},{"issue":"3","key":"10_CR4","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."},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-540-30140-0_25","volume-title":"Algorithms \u2013 ESA 2004","author":"V. Damerow","year":"2004","unstructured":"Damerow, V., Sohler, C.: Extreme points under random noise. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 264\u2013274. Springer, Heidelberg (2004)"},{"issue":"3","key":"10_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01(3), 195\u2013207 (1971)","journal-title":"Networks"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(84)90024-3","volume":"18","author":"M.E. Dyer","year":"1984","unstructured":"Dyer, M.E., Frieze, A.M.: A partitioning algorithm for minimum weighted euclidean matching. Inform. Process. Lett.\u00a018(2), 59\u201362 (1984)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"10_CR8","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. Oper. Res. Lett.\u00a037(2), 83\u201384 (2009)","journal-title":"Oper. Res. Lett."},{"key":"10_CR9","first-page":"1295","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M. Englert","year":"2007","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. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1295\u20131304. SIAM, Philadelphia (2007)"},{"key":"10_CR10","first-page":"257","volume-title":"The Traveling Salesman Problem and Its Variations","author":"A.M. Frieze","year":"2002","unstructured":"Frieze, A.M., Yukich, J.E.: Probabilistic analysis of the traveling salesman problem. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations, ch.7, pp. 257\u2013308. Kluwer, Dordrecht (2002)"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math.\u00a032(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR12","first-page":"252","volume-title":"Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M.J. Golin","year":"1996","unstructured":"Golin, M.J.: Limit theorems for minimum-weight triangulations, other euclidean functionals, and probabilistic recurrence relations. In: Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 252\u2013260. SIAM, Philadelphia (1996)"},{"key":"10_CR13","first-page":"369","volume-title":"The Traveling Salesman Problem and Its Variations","author":"D.S. Johnson","year":"2002","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.9, pp. 369\u2013443. Kluwer, Dordrecht (2002)"},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/net.3230240303","volume":"24","author":"K. Kalpakis","year":"1994","unstructured":"Kalpakis, K., Sherman, A.T.: Probabilistic analysis of an enhanced partitioning algorithm for the Steiner tree problem in R\n                \n                  d\n                . Networks\u00a024(3), 147\u2013159 (1994)","journal-title":"Networks"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"Karp, R.M.: Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res.\u00a02(3), 209\u2013224 (1977)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"10_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/S0167-7152(03)00037-3","volume":"62","author":"C.A. Le\u00f3n","year":"2003","unstructured":"Le\u00f3n, C.A., Perron, F.: Extremal properties of sums of Bernoulli random variables. Statist. Probab. Lett.\u00a062(4), 345\u2013354 (2003)","journal-title":"Statist. Probab. Lett."},{"key":"10_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"issue":"3","key":"10_CR18","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. Theoret. Comput. Sci.\u00a04(3), 237\u2013244 (1977)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems related to the traveling salesman problem. J. Algorithms\u00a05(2), 231\u2013246 (1984)","journal-title":"J. Algorithms"},{"issue":"8","key":"10_CR20","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/net.3230240802","volume":"24","author":"S. Ravada","year":"1994","unstructured":"Ravada, S., Sherman, A.T.: Experimental evaluation of a partitioning algorithm for the steiner tree problem in R\n                2 and R\n                3. Networks\u00a024(8), 409\u2013415 (1994)","journal-title":"Networks"},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1214\/aoap\/1177005364","volume":"3","author":"W.T. Rhee","year":"1993","unstructured":"Rhee, W.T.: A matching problem and subadditive euclidean functionals. Ann. Appl. Probab.\u00a03(3), 794\u2013801 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"10_CR22","first-page":"681","volume-title":"Proc. 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS)","author":"H. R\u00f6glin","year":"2009","unstructured":"R\u00f6glin, H., Teng, S.-H.: Smoothed analysis of multiobjective optimization. In: Proc. 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 681\u2013690. IEEE, Los Alamitos (2009)"},{"issue":"3","key":"10_CR23","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":"10_CR24","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. Comm. ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Comm. ACM"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-540-77050-3_41","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"A. Srivastav","year":"2007","unstructured":"Srivastav, A., Werth, S.: Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol.\u00a04855, pp. 497\u2013507. Springer, Heidelberg (2007)"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1287\/moor.6.3.374","volume":"6","author":"J. Michael Steele","year":"1981","unstructured":"Michael Steele, J.: Complete convergence of short paths in Karp\u2019s algorithm for the TSP. Math. Oper. Res.\u00a06, 374\u2013378 (1981)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"10_CR27","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J. Michael Steele","year":"1981","unstructured":"Michael Steele, J.: Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab.\u00a09(3), 365\u2013376 (1981)","journal-title":"Ann. Probab."},{"key":"10_CR28","series-title":"CBMS-NSF Regional Conf. Series in Appl. Math.","volume-title":"Probability Theory and Combinatorial Optimization","author":"J. Michael Steele","year":"1987","unstructured":"Michael Steele, J.: Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conf. Series in Appl. Math., vol.\u00a069. SIAM, Philadelphia (1987)"},{"issue":"1","key":"10_CR29","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/0212008","volume":"12","author":"K.J. Supowit","year":"1983","unstructured":"Supowit, K.J., Reingold, E.M.: Divide and conquer heuristics for minimum weighted euclidean matching. SIAM J. Comput.\u00a012(1), 118\u2013143 (1983)","journal-title":"SIAM J. Comput."},{"key":"10_CR30","first-page":"320","volume-title":"Proc. 39th Ann. Symp. on Foundations of Computer Science (FOCS)","author":"K.R. Varadarajan","year":"1998","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: Proc. 39th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 320\u2013331. IEEE, Los Alamitos (1998)"},{"key":"10_CR31","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0093472","volume-title":"Probability Theory of Classical Euclidean Optimization Problems","author":"J.E. Yukich","year":"1998","unstructured":"Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol.\u00a01675. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T03:06:57Z","timestamp":1554001617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}