Clustering with diversity

Details Clustering with diversity Clustering with diversity

2010-04-17

arxiv.org/abs/1004.2968v2

Computer Science

Data Structures and Algorithms

Extended abstract accepted in ICALP 2010. Keywords: Approximation algorithm, k-center, k-anonymity, l-diversity

Scientific paper

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 $\ell$ points, all of which have distinct colors. We give a 2-approximation to this problem for any $\ell$ when the objective is to minimize the maximum radius of any cluster. We show that the approximation ratio is optimal unless $\mathbf{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.

Affiliated with

Also associated with

No associations

Rating

Clustering with diversity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Clustering with diversity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clustering with diversity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-69739