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) |