2010/04/17 by Jian Li, Li, Jian, Ke Yi +3
Business, Management and Accounting · Computer Science · #Bayesian Methods and Mixture Models #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management
paper · pdf · doi:10.48550/arxiv.1004.2968
openalex publication_date 2010/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the \em clustering with diversity problem: given a set of colored points in a metric space, partition them into clusters such that each cluster has at least ℓ points, all of which have distinct colors. We give a 2-approximation to this problem for any ℓ when the objective is to minimize the maximum radius of any cluster. We show that the approximation ratio is optimal unless P=NP, by providing a matching lower bound. Several extensions to our algorithm have also been developed for handling outliers. This problem is mainly motivated by applications in privacy-preserving data publication.