{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:34:59Z","timestamp":1725744899400},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_30","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"349-360","source":"Crossref","is-referenced-by-count":3,"title":["A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems"],"prefix":"10.1007","author":[{"given":"Radu","family":"Curticapean","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"30_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(87)90178-5","volume":"24","author":"R.P. Anstee","year":"1987","unstructured":"Anstee, R.P.: A polynomial algorithm for b-matchings: An alternative approach. Information Processing Letters\u00a024(3), 153\u2013157 (1987)","journal-title":"Information Processing Letters"},{"issue":"5","key":"30_CR2","doi-asserted-by":"crossref","first-page":"1","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. Journal of the ACM\u00a058(5), 19:1\u201319:31 (2011)","journal-title":"Journal of the ACM"},{"issue":"2","key":"30_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\u00a039(2), 766\u2013782 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"30_CR4","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D. Avis","year":"1983","unstructured":"Avis, D.: A survey of heuristics for the weighted matching problem. Networks\u00a013(4), 475\u2013493 (1983)","journal-title":"Networks"},{"issue":"1-2","key":"30_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2011.10.006","volume":"112","author":"P. Awasthi","year":"2012","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Center-based clustering under perturbation stability. Information Processing Letters\u00a0112(1-2), 49\u201354 (2012)","journal-title":"Information Processing Letters"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Correa, J.\u00c9.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Mathematics of Operations Research\u00a031, 31\u201349 (2006)","journal-title":"Mathematics of Operations Research"},{"issue":"5","key":"30_CR7","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1145\/876638.876640","volume":"50","author":"A. Barvinok","year":"2003","unstructured":"Barvinok, A., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM\u00a050(5), 641\u2013664 (2003)","journal-title":"J. ACM"},{"issue":"1","key":"30_CR8","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/moor.21.1.65","volume":"21","author":"A.I. Barvinok","year":"1996","unstructured":"Barvinok, A.I.: Two algorithmic results for the traveling salesman problem. Mathematics of Operations Research\u00a021(1), 65\u201384 (1996)","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"30_CR9","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\u00a035(4), 855\u2013881 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"30_CR10","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., Raghavendra Rao, B.V.: Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica\u00a066(2), 397\u2013418 (2013)","journal-title":"Algorithmica"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-22006-7_13","volume-title":"Automata, Languages and Programming","author":"E. Boros","year":"2011","unstructured":"Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic mean payoff games: Smoothed analysis and approximation schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 147\u2013158. Springer, Heidelberg (2011)"},{"issue":"3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K. Chen","year":"2009","unstructured":"Chen, K.: On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing\u00a039(3), 923\u2013947 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR13","unstructured":"Dasgupta, S.: The hardness of k-means clustering. Technical report cs2007-0890, University of California, San Diego (2007)"},{"issue":"5","key":"30_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0167-6377(84)90059-2","volume":"3","author":"M.E. Dyer","year":"1984","unstructured":"Dyer, M.E., Frieze, A.M., McDiarmid, C.J.H.: Partitioning heuristics for two geometric maximization problems. Operations Research Letters\u00a03(5), 267\u2013270 (1984)","journal-title":"Operations Research Letters"},{"key":"30_CR15","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP: Extended abstract. In: 18th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2007, pp. 1295\u20131304. SIAM (2007)"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/944618.944629","volume":"7","author":"S.P. Fekete","year":"2002","unstructured":"Fekete, S.P., Meijer, H., Rohe, A., Tietze, W.: Solving a \u201dhard\u201d problem to approximate an \u201deasy\u201d one: Heuristics for maximum matchings and maximum traveling salesman problems. ACM J. on Experimental Algorithmics.\u00a07, 11 (2002)","journal-title":"ACM J. on Experimental Algorithmics."},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: 23rd Ann. Symp. on Computational Geometry, SCG 2007, pp. 11\u201318. ACM (2007)","DOI":"10.1145\/1247069.1247072"},{"issue":"4","key":"30_CR18","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + \u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"2","key":"30_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H.N. Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. Journal of the ACM\u00a023(2), 221\u2013234 (1976)","journal-title":"Journal of the ACM"},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: 36th Ann. ACM Symp. on Theory of Computing, STOC 2004, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: 10th Annual Symp. on Computational Geometry, SCG 1994, pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"30_CR22","unstructured":"Karger, D., Onak, K.: Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. In: 18th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2007, pp. 1207\u20131216 (2007)"},{"key":"30_CR23","first-page":"289","volume-title":"16th Annual ACM Symp. on Theory of Computing, STOC 1984","author":"R.M. Karp","year":"1984","unstructured":"Karp, R.M., Luby, M., Marchetti-Spaccamela, A.: A probabilistic analysis of multidimensional bin packing problems. In: 16th Annual ACM Symp. on Theory of Computing, STOC 1984, pp. 289\u2013298. ACM, New York (1984)"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M. Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theoretical Computer Science\u00a0442, 13\u201321 (2012)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"30_CR25","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a020(2), 257 (1995)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"30_CR26","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. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"3","key":"30_CR27","doi-asserted-by":"publisher","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. The Annals of Probability\u00a09(3), 365\u2013376 (1981)","journal-title":"The Annals of Probability"},{"issue":"3","key":"30_CR28","doi-asserted-by":"crossref","first-page":"A85","DOI":"10.1007\/BF01919172","volume":"30","author":"M. Weber","year":"1986","unstructured":"Weber, M., Liebling, T.M.: Euclidean matching problems and the metropolis algorithm. Mathematical Methods of Operations Research\u00a030(3), A85\u2013A110 (1986)","journal-title":"Mathematical Methods of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:03:48Z","timestamp":1558011828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}