2024/01/10 by Thejaswi, Suhas, Gadekar, Ameet, Ordozgoiti, Bruno +1 · 2 citations
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2401.05502
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+ (2)/(e) + ε≈ 1.736, 1+(8)/(e) + ε≈ 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.