{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T06:44:41Z","timestamp":1649141081072},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,7,21]],"date-time":"2009-07-21T00:00:00Z","timestamp":1248134400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00224-009-9235-1","type":"journal-article","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T14:20:07Z","timestamp":1248099607000},"page":"416-442","source":"Crossref","is-referenced-by-count":1,"title":["Small Space Representations for Metric Min-sum k-Clustering and Their Applications"],"prefix":"10.1007","volume":"46","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,21]]},"reference":[{"key":"9235_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. In: Proc. 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 271\u2013286, 2006","DOI":"10.1145\/1132516.1132557"},{"issue":"3","key":"9235_CR2","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/S0895480102410973","volume":"16","author":"N. Alon","year":"2003","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. SIAM J. Discrete Math. 16(3), 393\u2013417 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9235_CR3","volume-title":"Current Trends in Combinatorial and Computational Geometry","author":"P.K. Agarwal","year":"2005","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets. In: Welzl, E. (ed.) Current Trends in Combinatorial and Computational Geometry. Cambridge University Press, New York (2005)"},{"key":"9235_CR4","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility location in sublinear time. In: Proc. 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 866\u2013877, 2005","DOI":"10.1007\/11523468_70"},{"key":"9235_CR5","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 250\u2013257, 2002","DOI":"10.1145\/509907.509947"},{"key":"9235_CR6","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 11\u201320, 2001","DOI":"10.1145\/380752.380754"},{"key":"9235_CR7","unstructured":"Berkhin, P.: Survey of clustering data mining techniques. Technical Report, Accrue Software, San Jose, CA (2002)"},{"key":"9235_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. In: Proc. 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 626\u2013635, 1997","DOI":"10.1145\/258533.258657"},{"key":"9235_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proc. 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 30\u201339, 2003","DOI":"10.1145\/780542.780548"},{"key":"9235_CR10","doi-asserted-by":"crossref","unstructured":"Chen, K.: On k-median clustering in high dimensions. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1177\u20131185, 2006","DOI":"10.1145\/1109557.1109687"},{"issue":"3","key":"9235_CR11","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1137\/S009753970444199X","volume":"34","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Sohler, C.: Abstract combinatorial programs and efficient property testers. SIAM J. Comput. 34(3), 580\u2013615 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9235_CR12","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1002\/rsa.20157","volume":"30","author":"A. Czumaj","year":"2007","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time approximation for clustering via random sampling. Random Struct. Algorithms 30(1\u20132), 226\u2013256 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"9235_CR13","first-page":"23","volume":"89","author":"A. Czumaj","year":"2006","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. Bull. EATCS 89, 23\u201347 (2006)","journal-title":"Bull. EATCS"},{"key":"9235_CR14","unstructured":"Fernandez de la Vega, W., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proc. 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 50\u201358, 2003"},{"issue":"4","key":"9235_CR15","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1006\/jcss.2001.1772","volume":"63","author":"W. Fernandez de la Vega","year":"2001","unstructured":"Fernandez de la Vega, W., Kenyon, C.: A randomized approximation scheme for metric MAX-CUT. J. Comput. Syst. Sci. 63(4), 531\u2013541 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9235_CR16","doi-asserted-by":"crossref","unstructured":"Fotakis, D.: Memoryless facility location in one pass. In: Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 608\u2013620, 2006","DOI":"10.1007\/11672142_50"},{"key":"9235_CR17","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 209\u2013217, 2005","DOI":"10.1145\/1060590.1060622"},{"key":"9235_CR18","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for Maximum Cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"9235_CR19","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"9235_CR20","unstructured":"Guha, S., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams. In: Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 359\u2013366, 2000"},{"key":"9235_CR21","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0166-218X(98)00100-0","volume":"89","author":"N. Gutmann-Beck","year":"1998","unstructured":"Gutmann-Beck, N., Hassin, R.: Approximation algorithms for min-sum p-clustering. Discrete Appl. Math. 89, 125\u2013142 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9235_CR22","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Clustering motion. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 84\u201393, 2001","DOI":"10.1109\/SFCS.2001.959883"},{"key":"9235_CR23","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for k-means and k-medians and their applications. In: Proc. 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 291\u2013300, 2004"},{"key":"9235_CR24","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. In: Proc. 21st Annual ACM Symposium on Computational Geometry (SoCG), pp. 126\u2013134, 2005","DOI":"10.1145\/1064092.1064114"},{"key":"9235_CR25","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Varadarajan, K.: Projective clustering in high dimensions using core-sets. In: Proc. 18th Annual ACM Symposium on Computational Geometry (SoCG), pp. 312\u2013318, 2002","DOI":"10.1145\/513400.513440"},{"key":"9235_CR26","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: Proc. 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 428\u2013434, 1999","DOI":"10.1145\/301250.301366"},{"key":"9235_CR27","unstructured":"Indyk, P.: High-dimensional computational geometry. PhD thesis, Stanford University (2000)"},{"key":"9235_CR28","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: Proc. 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 373\u2013380, 2004","DOI":"10.1145\/1007352.1007413"},{"issue":"3","key":"9235_CR29","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"A.K. Jain","year":"2003","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31(3), 264\u2013323 (2003)","journal-title":"ACM Comput. Surv."},{"key":"9235_CR30","doi-asserted-by":"crossref","unstructured":"Korn, F., Muthukrishnan, S., Srivastava, D.: Reverse nearest neighbor aggregates over data streams. In: Proc. 28th International Conference on Very Large Data Bases (VLDB), pp. 814\u2013825, 2002","DOI":"10.1016\/B978-155860869-6\/50077-9"},{"key":"9235_CR31","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1+\u03b5)-approximation algorithm for k-means clustering in any dimensions. In: Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 454\u2013462, 2004","DOI":"10.1109\/FOCS.2004.7"},{"key":"9235_CR32","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear time algorithms for clustering problems in any dimensions. In: Proc. 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 1374\u20131385, 2005","DOI":"10.1007\/11523468_111"},{"issue":"1\u20133","key":"9235_CR33","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1023\/B:MACH.0000033114.18632.e0","volume":"56","author":"R. Mettu","year":"2004","unstructured":"Mettu, R., Plaxton, G.: Optimal time bounds for approximate clustering. Machine Learning 56(1\u20133), 35\u201360 (2004)","journal-title":"Machine Learning"},{"key":"9235_CR34","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426\u2013431, 2001","DOI":"10.1109\/SFCS.2001.959917"},{"issue":"1\u20133","key":"9235_CR35","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1023\/B:MACH.0000033115.78247.f0","volume":"56","author":"A. Meyerson","year":"2004","unstructured":"Meyerson, A., O\u2019Callaghan, L., Plotkin, S.: A k-median algorithm with running time independent of data size. Machine Learning 56(1\u20133), 61\u201387 (2004)","journal-title":"Machine Learning"},{"key":"9235_CR36","unstructured":"Mishra, N., Oblinger, D., Pitt, L.: Sublinear time approximate clustering. In: Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 439\u2013447, 2001"},{"key":"9235_CR37","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2) (2005)","DOI":"10.1561\/0400000002"},{"key":"9235_CR38","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. Electronic Colloquium on Computational Complexity (ECCC), Report No. 10 (2004)"},{"key":"9235_CR39","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y.: On average distortion of embedding metrics into the line and into L 1. In: Proc. 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 456\u2013462, 2003","DOI":"10.1145\/780542.780609"},{"key":"9235_CR40","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM 23, 555\u2013566 (1976)","journal-title":"J. ACM"},{"key":"9235_CR41","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization. In: Proc. 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 547\u2013555, 2000"},{"issue":"2","key":"9235_CR42","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/S0097539701388884","volume":"34","author":"M. Thorup","year":"2005","unstructured":"Thorup, M.: Quick k-median, k-center, and facility location for sparse graphs. SIAM J. Comput. 34(2), 405\u2013432 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9235_CR43","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/rsa.3240060403","volume":"6","author":"T. Tokuyama","year":"1995","unstructured":"Tokuyama, T., Nakano, J.: Geometric algorithms for the minimum cost assignment problem. Random Struct. Algorithms 6(4), 393\u2013406 (1995)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"9235_CR44","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TNN.2005.845141","volume":"16","author":"R. Xu","year":"2005","unstructured":"Xu, R., II Wunsch, D.: Survey of clustering algorithms. IEEE Trans. Neural Netw. 16(3), 645\u2013678 (2005)","journal-title":"IEEE Trans. Neural Netw."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9235-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9235-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9235-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:38Z","timestamp":1558684298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9235-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,21]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9235"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9235-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,21]]}}}