Provable imbalanced point clustering
Abstract
Abstract We suggest efficient and provable methods to compute an approximation for imbalanced point clustering, that is, fitting k -centers to a set of points in $$\mathbb {R}^d$$ , for any $$d,k\ge 1$$ , where we aim to minimize the variance over the clusters. To this end, we utilize coresets , which, in the context of the paper, are essentially weighted sets of points in $$\mathbb {R}^d$$ that approximate the fitting loss for every model in a given set, up to a multiplicative factor of $$1\pm \varepsilon $$ . We provide experiments that show the empirical contribution of our suggested methods for real images (novel and reference), synthetic data, and real-world data. We also propose choice clustering, which, by combining clustering algorithms, yields better performance than each one separately.
Fields of Study & Subjects
Data Management and Algorithms
Anomaly Detection Techniques and Applications
Publication details
- Journal / source
- Cryptography and Communications
- Publisher
- Springer Science and Business Media LLC
- Volume
- 18
- Issue
- 6
- Pages
- 2235-2271
- Publication date
- 2 July 2026
- Language
- EN