Provable Imbalanced Point Clustering
<|reference_start|>Provable Imbalanced Point Clustering: 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\geq 1$. To this end, we utilize \emph{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 [Section 3 and Section E in the appendix] 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.<|reference_end|>
@article{denisov2024provable,
    title={Provable Imbalanced Point Clustering},
    author={David Denisov, Dan Feldman, Shlomi Dolev, and Michael Segal},
    journal={arXiv preprint arXiv:2408.14225},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.14225},
    primaryClass={cs.LG}
}