Sublinear-time approximation algorithms for clustering via random sampling

C. Sohler, A. Czumaj, Random Structures & Algorithms 30 (2007) 226-- 256.

Download
No fulltext has been uploaded.
Journal Article | English
Author
;
Abstract
We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007A preliminary extended abstract of this work appeared in Proceedings of the 31st Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 396407, 2004.
Publishing Year
Journal Title
Random Structures & Algorithms
Volume
30
Issue
1-2
Page
226 -- 256
LibreCat-ID

Cite this

Sohler C, Czumaj A. Sublinear-time approximation algorithms for clustering via random sampling. Random Structures & Algorithms. 2007;30(1-2):226-- 256.
Sohler, C., & Czumaj, A. (2007). Sublinear-time approximation algorithms for clustering via random sampling. Random Structures & Algorithms, 30(1–2), 226-- 256.
@article{Sohler_Czumaj_2007, title={Sublinear-time approximation algorithms for clustering via random sampling}, volume={30}, number={1–2}, journal={Random Structures & Algorithms}, author={Sohler, Christian and Czumaj, Artur}, year={2007}, pages={226-- 256} }
Sohler, Christian, and Artur Czumaj. “Sublinear-Time Approximation Algorithms for Clustering via Random Sampling.” Random Structures & Algorithms 30, no. 1–2 (2007): 226-- 256.
C. Sohler and A. Czumaj, “Sublinear-time approximation algorithms for clustering via random sampling,” Random Structures & Algorithms, vol. 30, no. 1–2, pp. 226-- 256, 2007.
Sohler, Christian, and Artur Czumaj. “Sublinear-Time Approximation Algorithms for Clustering via Random Sampling.” Random Structures & Algorithms, vol. 30, no. 1–2, 2007, pp. 226-- 256.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar