{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:48Z","timestamp":1760202648619},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1007\/s00453-012-9643-5","type":"journal-article","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T12:08:02Z","timestamp":1334059682000},"page":"397-418","source":"Crossref","is-referenced-by-count":12,"title":["Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals"],"prefix":"10.1007","volume":"66","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","published-online":{"date-parts":[[2012,4,11]]},"reference":[{"key":"9643_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"issue":"2","key":"9643_CR2","first-page":"181","volume":"28","author":"B. Anthes","year":"2001","unstructured":"Anthes, B., R\u00fcschendorf, L.: On the weighted Euclidean matching problem in $\\mathbb{R}^{d}$ . Appl. Math. 28(2), 181\u2013190 (2001)","journal-title":"Appl. Math."},{"issue":"5","key":"9643_CR3","doi-asserted-by":"crossref","DOI":"10.1145\/2027216.2027217","volume":"58","author":"D. Arthur","year":"2011","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. J. ACM 58(5), 19 (2011)","journal-title":"J. ACM"},{"issue":"3","key":"9643_CR4","doi-asserted-by":"crossref","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. Syst. Sci. 69(3), 306\u2013329 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9643_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/978-3-642-22300-6_10","volume-title":"Proc. of the 12th Algorithms and Data Structures Symposium (WADS)","author":"M. Bl\u00e4ser","year":"2011","unstructured":"Bl\u00e4ser, M., Manthey, B., Rao, B.V.R.: Smoothed analysis of partitioning algorithms for Euclidean functionals. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) Proc. of the 12th Algorithms and Data Structures Symposium (WADS). Lecture Notes in Computer Science, vol.\u00a06844, pp.\u00a0110\u2013121. Springer, Berlin (2011)"},{"key":"9643_CR6","unstructured":"Damerow, V., Manthey, B., Meyer auf der\u00a0Heide, F., R\u00e4cke, H., Scheideler, C., Sohler, C., Tantau, T.: Smoothed analysis of left-to-right maxima with applications. ACM Trans. Algorithms (to appear)"},{"key":"9643_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-540-30140-0_25","volume-title":"Proc. of the 12th Ann. European Symp. on Algorithms (ESA)","author":"V. Damerow","year":"2004","unstructured":"Damerow, V., Sohler, C.: Extreme points under random noise. In: Albers, S., Radzik, T. (eds.) Proc. of the 12th Ann. European Symp. on Algorithms (ESA). Lecture Notes in Computer Science, vol.\u00a03221, pp.\u00a0264\u2013274. Springer, Berlin (2004)"},{"issue":"3","key":"9643_CR8","doi-asserted-by":"crossref","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 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"issue":"2&3","key":"9643_CR9","first-page":"121","volume":"7","author":"D.-Z. Du","year":"1992","unstructured":"Du, D.-Z., Hwang, F.K.: A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica 7(2&3), 121\u2013135 (1992)","journal-title":"Algorithmica"},{"issue":"2","key":"9643_CR10","doi-asserted-by":"crossref","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. Inf. Process. Lett. 18(2), 59\u201362 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9643_CR11","doi-asserted-by":"crossref","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. 37(2), 83\u201384 (2009)","journal-title":"Oper. Res. Lett."},{"key":"9643_CR12","first-page":"1295","volume-title":"Proc. of the 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. of the 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp.\u00a01295\u20131304. SIAM, Philadelphia (2007)"},{"key":"9643_CR13","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, pp.\u00a0257\u2013308. Kluwer Academic, Dordrecht (2002). Chapter\u00a07"},{"issue":"4","key":"9643_CR14","doi-asserted-by":"crossref","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. 32(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"9643_CR15","first-page":"252","volume-title":"Proc. of the 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. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp.\u00a0252\u2013260. SIAM, Philadelphia (1996)"},{"key":"9643_CR16","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, pp.\u00a0369\u2013443. Kluwer Academic, Dordrecht (2002). Chapter\u00a09"},{"issue":"3","key":"9643_CR17","doi-asserted-by":"crossref","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\u00a0R d . Networks 24(3), 147\u2013159 (1994)","journal-title":"Networks"},{"issue":"3","key":"9643_CR18","doi-asserted-by":"crossref","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. 2(3), 209\u2013224 (1977)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9643_CR19","doi-asserted-by":"crossref","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. Stat. Probab. Lett. 62(4), 345\u2013354 (2003)","journal-title":"Stat. Probab. Lett."},{"issue":"6","key":"9643_CR20","doi-asserted-by":"crossref","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\u2013Inf. Technol. 53(6), 280\u2013286 (2011)","journal-title":"it\u2013Inf. Technol."},{"key":"9643_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"issue":"3","key":"9643_CR22","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9643_CR23","doi-asserted-by":"crossref","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 5(2), 231\u2013246 (1984)","journal-title":"J. Algorithms"},{"issue":"8","key":"9643_CR24","doi-asserted-by":"crossref","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 2 and R 3. Networks 24(8), 409\u2013415 (1994)","journal-title":"Networks"},{"issue":"3","key":"9643_CR25","doi-asserted-by":"crossref","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. 3(3), 794\u2013801 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"9643_CR26","first-page":"681","volume-title":"Proc. of the 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. of the 50th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a0681\u2013690. IEEE Press, New York (2009)"},{"issue":"3","key":"9643_CR27","doi-asserted-by":"crossref","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 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"9643_CR28","doi-asserted-by":"crossref","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 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"9643_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/978-3-540-77050-3_41","volume-title":"Proc. of the 27th Int. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","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.) Proc. of the 27th Int. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Lecture Notes in Computer Science, vol.\u00a04855, pp.\u00a0497\u2013507. Springer, Berlin (2007)"},{"key":"9643_CR30","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1287\/moor.6.3.374","volume":"6","author":"J.M. Steele","year":"1981","unstructured":"Steele, J.M.: Complete convergence of short paths in Karp\u2019s algorithm for the TSP. Math. Oper. Res. 6, 374\u2013378 (1981)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9643_CR31","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1214\/aop\/1176994411","volume":"9","author":"J.M. Steele","year":"1981","unstructured":"Steele, J.M.: Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab. 9(3), 365\u2013376 (1981)","journal-title":"Ann. Probab."},{"key":"9643_CR32","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","volume-title":"Probability Theory and Combinatorial Optimization","author":"J.M. Steele","year":"1987","unstructured":"Steele, J.M.: Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a069. SIAM, Philadelphia (1987)"},{"issue":"1","key":"9643_CR33","doi-asserted-by":"crossref","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. 12(1), 118\u2013143 (1983)","journal-title":"SIAM J. Comput."},{"key":"9643_CR34","first-page":"320","volume-title":"Proc. of the 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. of the 39th Ann. Symp. on Foundations of Computer Science (FOCS), pp.\u00a0320\u2013331. IEEE Press, New York (1998)"},{"key":"9643_CR35","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, Berlin (1998)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9643-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T13:05:31Z","timestamp":1497963931000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9643-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,11]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["9643"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9643-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,11]]}}}