×

Smaller coresets for \(k\)-median and \(k\)-means clustering. (English) Zbl 1106.68112

Summary: In this paper we show that there exists a \((k,\varepsilon)\)-coreset for \(k\)-median and \(k\)-means clustering of \(n\) points in \(\mathbb{R}^d\), which is of size independent of \(n\). In particular, we construct a \((k,\varepsilon)\)-coreset of size \(O(k^2/\varepsilon^d)\) for \(k\)-median clustering, and of size \(O(k^3/\varepsilon^{d+1})\) for \(k\)-means clustering.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI