{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:14:06Z","timestamp":1725542046167},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642106309"},{"type":"electronic","value":"9783642106316"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_103","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T07:03:43Z","timestamp":1259910223000},"page":"1024-1033","source":"Crossref","is-referenced-by-count":6,"title":["Worst-Case and Smoothed Analysis of k-Means\u00a0Clustering with Bregman Divergences"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"103_CR1","doi-asserted-by":"crossref","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Coresets and approximate clustering for Bregman divergences. In: Proc. of the 20th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1088\u20131097 (2009)","DOI":"10.1137\/1.9781611973068.118"},{"key":"103_CR2","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Sohler, C.: Clustering for metric and non-metric distance measures. In: Proc. of the 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 799\u2013808 (2008)"},{"key":"103_CR3","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. In: Proc. of the 50th Ann. IEEE Symp. on Found. of Computer Science, FOCS (to appear, 2009)"},{"issue":"2","key":"103_CR4","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"},{"key":"103_CR5","first-page":"1705","volume":"6","author":"A. Banerjee","year":"2005","unstructured":"Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.: Clustering with Bregman divergences. Journal of Machine Learning Research\u00a06, 1705\u20131749 (2005)","journal-title":"Journal of Machine Learning Research"},{"key":"103_CR6","unstructured":"Berkhin, P.: Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, USA (2002)"},{"key":"103_CR7","doi-asserted-by":"publisher","first-page":"1265","DOI":"10.1162\/153244303322753661","volume":"3","author":"I.S. Dhillon","year":"2003","unstructured":"Dhillon, I.S., Mallela, S., Kumar, R.: A divisive information-theoretic feature clustering algorithm for text classification. Journal of Machine Learning Research\u00a03, 1265\u20131287 (2003)","journal-title":"Journal of Machine Learning Research"},{"key":"103_CR8","volume-title":"Pattern Classification","author":"R.O. Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. John Wiley & Sons, Chichester (2000)"},{"key":"103_CR9","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol.\u00a0II. John Wiley & Sons, Chichester (1971)"},{"issue":"4","key":"103_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1109\/TASSP.1980.1163421","volume":"28","author":"R.M. Gray","year":"1980","unstructured":"Gray, R.M., Buzo, A., Gray Jr., A.H., Matsuyama, Y.: Distortion measures for speech processing. IEEE Transactions on Acoustics, Speech, and Signal Processing\u00a028(4), 367\u2013376 (1980)","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal Processing"},{"issue":"6","key":"103_CR11","first-page":"1199","volume":"E83-D","author":"M. Inaba","year":"2000","unstructured":"Inaba, M., Katoh, N., Imai, H.: Variance-based k-clustering algorithms by Voronoi diagrams and randomization. IEICE Transactions on Information and Systems\u00a0E83-D(6), 1199\u20131206 (2000)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"2","key":"103_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S.P. Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Transactions on Information Theory\u00a028(2), 129\u2013137 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"key":"103_CR13","doi-asserted-by":"crossref","unstructured":"Manthey, B., R\u00f6glin, H.: Improved smoothed analysis of the k-means method. In: Proc. of the 20th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 461\u2013470 (2009)","DOI":"10.1137\/1.9781611973068.51"},{"issue":"3","key":"103_CR14","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"},{"key":"103_CR15","doi-asserted-by":"crossref","unstructured":"Vattani, A.: k-means requires exponentially many iterations even in the plane. In: Proc. of the 25th ACM Symp. on Computational Geometry (SoCG), pp. 324\u2013332 (2009)","DOI":"10.1145\/1542362.1542419"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_103.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:36:41Z","timestamp":1619782601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_103","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}