The MPFCC Algorithm: A Model-Based Approach for Fair-Capacitated Clustering

Clustering is the process of grouping similar objects based on their features. In many real-world clustering applications where the objects refer to persons, there is a great need to ensure that the resulting clusters are fair and unbiased. Such applications have led to the emergence of novel types of clustering problems. We consider here the fair-capacitated clustering problem which consists of partitioning a set of objects into a predefined number of clusters subject to fairness and cardinality constraints. The state-of-the-art algorithm for this problem considers the fairness and the cardinality constraints in two separate steps. We introduce here a new model-based approach that considers the two types of constraints simultaneously. In a computational comparison based on benchmark instances from the literature, we demonstrate that our algorithm finds substantially better solutions than the state-of-the-art algorithm in similar running time.