{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:51Z","timestamp":1725558411109},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_21","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T07:00:50Z","timestamp":1276153250000},"page":"212-223","source":"Crossref","is-referenced-by-count":8,"title":["Bregman Clustering for Separable Instances"],"prefix":"10.1007","author":[{"given":"Marcel R.","family":"Ackermann","sequence":"first","affiliation":[]},{"given":"Johannes","family":"Bl\u00f6mer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC\u00a0\u201998), pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/3-540-48481-7_33","volume-title":"Algorithms - ESA\u201999","author":"S.G. Kolliopoulos","year":"1999","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean \u03ba-median problem. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 378\u2013389. Springer, Heidelberg (1999)"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902), pp. 250\u2013257. Association for Computing Machinery (2002)","DOI":"10.1145\/509943.509947"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904), pp. 291\u2013300. Association for Computing Machinery (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1007\/11523468_111","volume-title":"Automata, Languages and Programming","author":"A. Kumar","year":"2005","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear time algorithms for clustering problems in any dimensions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1374\u20131385. Springer, Heidelberg (2005)"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Chen, K.: On k-median clustering in high dimensions. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201906), pp. 1177\u20131185. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109687"},{"issue":"1","key":"21_CR7","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"J. Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek, J.: On approximate geometric k-clustering. Discrete and Computational Geometry\u00a024(1), 61\u201384 (2000)","journal-title":"Discrete and Computational Geometry"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Fernandez de la Vega, W., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC\u201903), pp. 50\u201358. Association for Computing Machinery (2003)","DOI":"10.1145\/780542.780550"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1109\/FOCS.2004.7","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u00a0\u201904)","author":"A. Kumar","year":"2004","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1+\u03b5)-approximation algorithm for k-means clustering in any dimensions. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u00a0\u201904), pp. 454\u2013462. IEEE Computer Society, Los Alamitos (2004)"},{"issue":"3","key":"21_CR10","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":"21_CR11","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proceedings of the 23rd ACM Symposium on Computational Geometry (SCG\u00a0\u201907), pp. 11\u201318. Association for Computing Machinery (2007)","DOI":"10.1145\/1247069.1247072"},{"key":"#cr-split#-21_CR12.1","unstructured":"Ackermann, M.R., Bl??mer, J., Sohler, C.: Clustering for metric and non-metric distance measures. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA?????08), pp. 799???808. Society for Industrial and Applied Mathematics (2008);"},{"key":"#cr-split#-21_CR12.2","unstructured":"Full version to appear in ACM Transactions on Algorithms (special issue on SODA?????08)."},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Coresets and approximate clustering for Bregman divergences. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), pp. 1088\u20131097. Society for Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9781611973068.118"},{"issue":"2","key":"21_CR14","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":"21_CR15","volume-title":"Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS\u00a0\u201909)","author":"D. Arthur","year":"2009","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. In: Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS\u00a0\u201909). IEEE Computer Society Press, Los Alamitos (2009) (to appear)"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Vattani, A.: k-means requires exponetially many iterations even in the plane. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SCG\u00a0\u201909), pp. 324\u2013332. Association for Computing Machinery (2009)","DOI":"10.1145\/1542362.1542419"},{"key":"21_CR17","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201907), pp. 1027\u20131035. Society for Industrial and Applied Mathematics (2007)"},{"key":"21_CR18","first-page":"165","volume-title":"Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS\u00a0\u201906)","author":"R. Ostrovsky","year":"2006","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. In: Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS\u00a0\u201906), pp. 165\u2013176. IEEE Computer Society, Los Alamitos (2006)"},{"key":"21_CR19","first-page":"15","volume-title":"Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u00a0\u201909)","author":"A. Aggarwal","year":"2009","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering. In: Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u00a0\u201909), pp. 15\u201328. Springer, Heidelberg (2009)"},{"key":"21_CR20","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"},{"issue":"7","key":"21_CR21","doi-asserted-by":"publisher","first-page":"2664","DOI":"10.1109\/TIT.2005.850145","volume":"51","author":"A. Banerjee","year":"2005","unstructured":"Banerjee, A., Guo, X., Wang, H.: On the optimality of conditional expectation as a Bregman predictor. IEEE Transactions on Information Theory\u00a051(7), 2664\u20132669 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1024","DOI":"10.1007\/978-3-642-10631-6_103","volume-title":"Algorithms and Computation","author":"B. Manthey","year":"2009","unstructured":"Manthey, B., R\u00f6glin, H.: Worst-case and smoothed analysis of k-means clustering with Bregman divergences. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1024\u20131033. Springer, Heidelberg (2009)"},{"key":"21_CR23","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-87481-2_11","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"R. Nock","year":"2008","unstructured":"Nock, R., Luosto, P., Kivinen, J.: Mixed Bregman clustering with approximation guarantees. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008, Part II. LNCS (LNAI), vol.\u00a05212, pp. 154\u2013169. Springer, Heidelberg (2008)"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Sra, S., Jegelka, S., Banerjee, A.: Approximation algorithms for Bregman clustering, co-clustering and tensor clustering. Technical Report MPIK-TR-177, Max Planck Institure for Biological Cybernetics (2008)","DOI":"10.1007\/978-3-642-04414-4_30"},{"issue":"7","key":"21_CR25","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","volume":"24","author":"T. Kanungo","year":"2002","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: Analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a024(7), 881\u2013892 (2002)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"21_CR26","first-page":"6","volume-title":"Proceedings of the 7th Pacific Symposium on Biocomputing (PSB\u00a0\u201902)","author":"A. Ben-Hur","year":"2002","unstructured":"Ben-Hur, A., Elisseeff, A., Guyon, I.: A stability based method for discovering structure in clustered data. In: Proceedings of the 7th Pacific Symposium on Biocomputing (PSB\u00a0\u201902), pp. 6\u201317. World Scientific, Singapore (2002)"},{"key":"21_CR27","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","volume":"7","author":"L.M. Bregman","year":"1967","unstructured":"Bregman, L.M.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics\u00a07, 200\u2013217 (1967)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"key":"21_CR28","unstructured":"Mahalanobis, P.C.: On the generalized distance in statistics. In: Proceedings of the National Institute of Sciences of India, vol.\u00a02(1), pp. 49\u201355. Indian National Science Academy (1936)"},{"key":"21_CR29","unstructured":"Ackermann, M.R.: Algorithms for the Bregman k-Median Problem. PhD thesis, University of Paderborn, Department of Computer Science (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:42:20Z","timestamp":1606167740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}