Provable imbalanced point clustering
David Denisov, Shlomi Dolev, Dan Feldman, Michael Segal · Cryptography and Communications · 2026
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.