@inproceedings{
arutyunova2024approximately,
title={Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering},
author={Anna Arutyunova and Jan Eube and Heiko R{\"o}glin and Melanie Schmidt and Sarah Sturm and Julian Wargalla},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=MFKfm5scHi}
}
As a major unsupervised learning method, clustering has received a lot of attention over multiple decades. The various clustering problems that have been studied intensively include, e.g., the $k$-means problem and the $k$-center problem. However, in applications, it is common that good clusterings should optimize multiple objectives (e.g., visualizing data on a map by clustering districts into areas that are both geographically compact but also homogeneous with respect to the data).  We study combinations of different objectives, for example optimizing $k$-center and $k$-means simultaneously or optimizing $k$-center with respect to two different metrics. Usually these objectives are conflicting and cannot be optimized simultaneously, making it necessary to find trade-offs. We develop novel algorithms for computing the set of Pareto-optimal solutions (approximately) for various combinations of two objectives. Our algorithms achieve provable approximation guarantees and we demonstrate in several experiments that the (approximate) Pareto set contains good clusterings that cannot be found by considering one of the objectives separately.
Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering
Anna Arutyunova Jan Eube Heiko Röglin Melanie Schmidt Sarah Sturm Julian Wargalla