摘要: We consider the clustering with diversity problem: given a set of colored points in metric space, partition them into clusters such that each cluster has at least l points, all which have distinct colors. give 2-approximation to this problem for any when objective is minimize maximum radius cluster. show approximation ratio optimal unless P = NP, by providing matching lower bound. Several extensions our algorithm also been developed handling outliers. This mainly motivated applications privacy-preserving data publication.
springer.com
arxiv.org
harvard.edu
core.ac.uk 
sci-hub.st 参考文章(34)
P. Samarati, Protecting respondents identities in microdata release IEEE Transactions on Knowledge and Data Engineering. ,vol. 13, pp. 1010- 1027 ,(2001) , 10.1109/69.971193
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu, Achieving anonymity via clustering symposium on principles of database systems. pp. 153- 162 ,(2006) , 10.1145/1142351.1142374
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil Vadhan, On the complexity of differentially private data release Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09. pp. 381- 390 ,(2009) , 10.1145/1536414.1536467
John E. Mitchell, Xiaoyun Ji, GRAPH PARTITION PROBLEMS WITH MINIMUM SIZE CONSTRAINTS ,(2004)
Xiaokui Xiao, Yufei Tao, M-invariance Proceedings of the 2007 ACM SIGMOD international conference on Management of data - SIGMOD '07. pp. 689- 700 ,(2007) , 10.1145/1247480.1247556
Claire Cardie, Kiri Wagstaff, Seth Rogers, Stefan Schrödl, Constrained K-means Clustering with Background Knowledge international conference on machine learning. pp. 577- 584 ,(2001)
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity ACM Transactions on Knowledge Discovery From Data. ,vol. 1, pp. 3- ,(2007) , 10.1145/1217299.1217302
A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam, L-diversity: privacy beyond k-anonymity international conference on data engineering. pp. 24- 24 ,(2006) , 10.1109/ICDE.2006.1
K. LeFevre, D.J. DeWitt, R. Ramakrishnan, Mondrian Multidimensional K-Anonymity international conference on data engineering. pp. 25- 25 ,(2006) , 10.1109/ICDE.2006.101
Arvind Arasu, Christopher Ré, Dan Suciu, None, Large-Scale Deduplication with Constraints Using Dedupalog 2009 IEEE 25th International Conference on Data Engineering. pp. 952- 963 ,(2009) , 10.1109/ICDE.2009.43