{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:36:22Z","timestamp":1760297782953,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_46","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"536-548","source":"Crossref","is-referenced-by-count":5,"title":["Small Space Representations for Metric Min-Sum k-Clustering and Their Applications"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1007\/11523468_70","volume-title":"Automata, Languages and Programming","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., et al.: Facility location in sublinear time. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 866\u2013877. Springer, Heidelberg (2005)"},{"key":"46_CR2","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: STOC, pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"46_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: STOC, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., et al.: Incremental clustering and dynamic information retrieval. In: STOC, pp. 626\u2013635 (1997)","DOI":"10.1145\/258533.258657"},{"key":"46_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: STOC, pp. 30\u201339 (2003)","DOI":"10.1145\/780542.780548"},{"key":"46_CR6","doi-asserted-by":"crossref","unstructured":"Chen, K.: On k-median clustering in high dimensions. In: SODA, pp. 1177\u20131185 (2006)","DOI":"10.1145\/1109557.1109687"},{"issue":"3","key":"46_CR7","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. SICOMP\u00a034(3), 580\u2013615 (2005)","journal-title":"SICOMP"},{"key":"46_CR8","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., et al.: Approximation schemes for clustering problems. In: STOC, pp. 50\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"key":"46_CR9","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: STOC, pp. 209\u2013217 (2005)","DOI":"10.1145\/1060590.1060622"},{"key":"46_CR10","doi-asserted-by":"crossref","unstructured":"Guha, S., et al.: Clustering data streams. In: FOCS, pp. 359\u2013366 (2000)","DOI":"10.1109\/SFCS.2000.892124"},{"key":"46_CR11","doi-asserted-by":"publisher","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 Applied Mathematics\u00a089, 125\u2013142 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for k-means and k-medians and their applications. In: STOC, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. In: SoCG, pp. 126\u2013134 (2005)","DOI":"10.1145\/1064092.1064114"},{"key":"46_CR14","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: STOC, pp. 428\u2013434 (1999)","DOI":"10.1145\/301250.301366"},{"key":"46_CR15","unstructured":"Indyk, P.: High-Dimensional Computational Geometry. PhD thesis, Stanford (2000)"},{"key":"46_CR16","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: STOC, pp. 373\u2013380 (2004)","DOI":"10.1145\/1007352.1007413"},{"key":"46_CR17","doi-asserted-by":"crossref","unstructured":"Indyk, P., Matou\u0161ek, J.: Low-distortion embeddings of finite metric spaces. In: Handbook of Discrete and Computational Geometry, 2nd edn., pp. 177\u2013196 (2004)","DOI":"10.1201\/9781420035315.ch8"},{"key":"46_CR18","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1\u2009+\u2009\u03b5)-approximation algorithm for k-means clustering in any dimensions. In: FOCS, pp. 454\u2013462 (2004)","DOI":"10.1109\/FOCS.2004.7"},{"key":"46_CR19","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., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1374\u20131385. Springer, Heidelberg (2005)"},{"issue":"1-3","key":"46_CR20","doi-asserted-by":"publisher","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\u00a056(1-3), 35\u201360 (2004)","journal-title":"Machine Learning"},{"issue":"1\u20133","key":"46_CR21","doi-asserted-by":"publisher","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\u00a056(1\u20133), 61\u201387 (2004)","journal-title":"Machine Learning"},{"key":"46_CR22","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. JACM\u00a023, 555\u2013566 (1976)","journal-title":"JACM"},{"key":"46_CR23","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization. In: STOC, pp. 547\u2013555 (2000)","DOI":"10.1145\/335305.335373"},{"issue":"2","key":"46_CR24","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. SICOMP\u00a034(2), 405\u2013432 (2005)","journal-title":"SICOMP"},{"issue":"4","key":"46_CR25","doi-asserted-by":"publisher","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 Structures and Algorithms\u00a06(4), 393\u2013406 (1995)","journal-title":"Random Structures and Algorithms"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T15:49:18Z","timestamp":1737042558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_46","relation":{},"subject":[]}}