# Can Evolutionary Clustering Have Theoretical Guarantees?

arXiv: https://arxiv.org/abs/2212.01771 · HTML: https://mlsanity.com/paper/2212.01771/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 71 references that are in the map.
- First posted on arXiv 4 Dec 2022.

## Builds on (most cited first, 15 of 15)

- [Large-Scale Evolution of Image Classifiers](https://mlsanity.com/paper/1703.01041/) (2017)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning](https://mlsanity.com/paper/1712.06567/) (2017)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)
- [Runtime Analysis of RLS and (1+1) EA for the Dynamic Weighted Vertex Cover Problem](https://mlsanity.com/paper/1903.02195/) (2019)
- [On the Robustness of Median Sampling in Noisy Evolutionary Optimization](https://mlsanity.com/paper/1907.13100/) (2019)

## Abstract (arXiv)

Clustering is a fundamental problem in many areas, which aims to partition a given data set into groups based on some distance measure, such that the data points in the same group are similar while that in different groups are dissimilar. Due to its importance and NP-hardness, a lot of methods have been proposed, among which evolutionary algorithms are a class of popular ones. Evolutionary clustering has found many successful applications, but all the results are empirical, lacking theoretical support. This paper fills this gap by proving that the approximation performance of the GSEMO (a simple multi-objective evolutionary algorithm) for solving four formulations of clustering, i.e., k-tMM, k-center, discrete k-median and k-means, can be theoretically guaranteed. Furthermore, we consider clustering under fairness, which tries to avoid algorithmic bias, and has recently been an important research topic in machine learning. We prove that for discrete k-median clustering under individual fairness, the approximation performance of the GSEMO can be theoretically guaranteed with respect to both the objective function and the fairness constraint.