{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:16:23Z","timestamp":1774941383499,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_35","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"396-407","source":"Crossref","is-referenced-by-count":8,"title":["Sublinear-Time Approximation for Clustering Via Random Sampling"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: 30th STOC, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: 33rd STOC, pp. 21\u201330 (2001)","DOI":"10.1145\/380752.380755"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In: 33rd STOC, pp. 11\u201320 (2001)","DOI":"10.1145\/380752.380754"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th FOCS, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"#cr-split#-35_CR5.1","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: 31st STOC, pp. 1\u201310 (1999);","DOI":"10.1145\/301250.301257"},{"key":"#cr-split#-35_CR5.2","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: 12th SODA, pp. 642\u2013651 (2001)"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: 35th STOC, pp. 30\u201339 (2003)","DOI":"10.1145\/780542.780548"},{"key":"35_CR7","unstructured":"Chazelle, B.: Who says you have to look at the input? The brave new world of sublinear computing? In: 15th SODA, p. 134 (2004)"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Fernandez de la Vega, W., Karpinski, M., Kenyon, C.: andY. Rabani. Polynomial time approximation schemes for metric min-sum clustering. In: 35th STOC, pp. 50\u201358 (2003)","DOI":"10.1145\/780547.780550"},{"key":"35_CR9","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":"35_CR10","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: Coresets for k-means and k-median clustering and their applications. In: 36th STOC (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: 31st STOC, pp. 428\u2013434 (1999)","DOI":"10.1145\/301250.301366"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P.: A sublinear time approximation scheme for clustering in metric spaces. In: 40th FOCS, pp. 154\u2013159 (1999)","DOI":"10.1109\/SFFCS.1999.814587"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: 34th STOC, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: 40th FOCS, pp. 2\u201313 (1999)","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"35_CR15","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 k-median problems. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 378\u2013389. Springer, Heidelberg (1999)"},{"issue":"4","key":"35_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/954092.954103","volume":"34","author":"R. Kumar","year":"2003","unstructured":"Kumar, R., Rubinfeld, R.: Sublinear time algorithms. SIGACT News\u00a034(4), 57\u201367 (2003)","journal-title":"SIGACT News"},{"key":"35_CR17","unstructured":"Mettu, R.R., Plaxton, C.G.: Optimal time bounds for approximate clustering. In: 18th Conference on Uncertainty in Artificial Intelligence (UAI), August 2002, pp. 344\u2013351 (2002)"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"Meyerson, A., O\u2019Callaghan, L., Plotkin, S.: A k-median algorithm with running time independent of data size. Journal of Machine Learning (2004)","DOI":"10.1023\/B:MACH.0000033115.78247.f0"},{"key":"35_CR19","unstructured":"Mishra, N., Oblinger, D., Pitt, L.: Sublinear time approximate clustering. In: 12th SODA, pp. 439\u2013447 (2001)"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization. In: 32nd STOC, pp. 547\u2013555 (2000)","DOI":"10.1145\/335305.335373"},{"key":"35_CR21","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"},{"issue":"4","key":"35_CR22","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","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:23:55Z","timestamp":1605759835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}