On k-Median clustering in high dimensions
Ke Chen · 2006
We study approximation algorithms for k-median clustering. We obtain small coresets for k-median clustering in metric spaces as well as in Euclidean spaces. Specifically, in IR d, those coresets are of size with only polynomial dependency on d. This leads to a (1 + ε)-approximation algorithm for k-median clustering in IR d, with running time O(ndk + 2 (k/ε)O(1) d2nσ), for any σ>0. This is an improvement over previous results [5, 20, 21]. We also provide fast constant factor approximation algorithms for k-median clustering in finite metric spaces. We use those coresets to compute (1 + ɛ)approximation k-median clustering in the streaming model of computation, using only O(k2dɛ−2 log 8 n) space, where the points are taken from IR d. This is the first streaming algorithm, for this problem, that has space complexity with only polynomial dependency on the dimension. 1