Diversity-aware clustering: Computational Complexity and Approximation Algorithms

Abstract

In this work, we study diversity-aware clustering problems where the data points are associated with multiple attributes resulting in intersecting groups. A clustering solution needs to ensure that the number of chosen cluster centers from each group should be within the range defined by a lower and upper bound threshold for each group, while simultaneously minimizing the clustering objective, which can be either k-median, k-means or k-supplier. We study the computational complexity of the proposed problems, offering insights into their NP-hardness, polynomial-time inapproximability, and fixed-parameter intractability. We present parameterized approximation algorithms with approximation ratios 1+ 2e + 1.736, 1+8e + 3.943, and 5 for diversity-aware k-median, diversity-aware k-means and diversity-aware k-supplier, respectively. Assuming Gap-ETH, the approximation ratios are tight for the diversity-aware k-median and diversity-aware k-means problems. Our results imply the same approximation factors for their respective fair variants with disjoint groups -- fair k-median, fair k-means, and fair k-supplier -- with lower bound requirements.

Tasks

Reproductions