Document Open Access Logo

Privacy Preserving Clustering with Constraints

Authors Clemens Rösner, Melanie Schmidt

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.96.pdf
  • Filesize: 409 kB
  • 14 pages

Document Identifiers

Author Details

Clemens Rösner
  • Department of Theoretical Computer Science, University of Bonn, Germany
Melanie Schmidt
  • Department of Theoretical Computer Science, University of Bonn, Germany

Cite AsGet BibTex

Clemens Rösner and Melanie Schmidt. Privacy Preserving Clustering with Constraints. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 96:1-96:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.96

Abstract

The k-center problem is a classical combinatorial optimization problem which asks to find k centers such that the maximum distance of any input point in a set P to its assigned center is minimized. The problem allows for elegant 2-approximations. However, the situation becomes significantly more difficult when constraints are added to the problem. We raise the question whether general methods can be derived to turn an approximation algorithm for a clustering problem with some constraints into an approximation algorithm that respects one constraint more. Our constraint of choice is privacy: Here, we are asked to only open a center when at least l clients will be assigned to it. We show how to combine privacy with several other constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Clustering
  • k-center
  • Constraints
  • Privacy
  • Lower Bounds
  • Fairness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation algorithm for the facility location problem with uniform capacities. Mathematical Programming, 141(1-2):527-547, 2013. Google Scholar
  2. Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu. Approximation algorithms for k-anonymity. In Proceedings of the International Conference on Database Theory (ICDT 2005), November 2005. URL: http://ilpubs.stanford.edu:8090/645/.
  3. Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Dilys Thomas, Krishnaram Kenthapadi, Samir Khuller, and An Zhu. Achieving anonymity via clustering. ACM Transaction on Algorithms, 6(3):49:1-49:19, 2010. Google Scholar
  4. Sara Ahmadian and Chaitanya Swamy. Approximation algorithms for clustering problems with lower bounds and outliers. In 43rd International Colloquium on Automata, Languages, and Programming, (ICALP), pages 69:1-69:15, 2016. Google Scholar
  5. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Mathematical Programming, 154(1-2):29-53, 2015. Google Scholar
  6. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. Google Scholar
  7. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In 20th Annual European Symposium on Algorithms (ESA), pages 133-144, 2012. Google Scholar
  8. Judit Bar-Ilan, Guy Kortsarz, and David Peleg. How to allocate network centers. Journal of Algorithms, 15(3):385-415, 1993. Google Scholar
  9. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2):23:1-23:31, 2017. Google Scholar
  10. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 67, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  11. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149, 2002. Google Scholar
  12. Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA), pages 642-651, 2001. Google Scholar
  13. Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27-52, 2016. Google Scholar
  14. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (NIPS), pages 5036-5044, 2017. Google Scholar
  15. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 273-282, 2012. Google Scholar
  16. Marek Cygan and Tomasz Kociumaka. Constant factor approximation for capacitated k-center with outliers. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pages 251-262, 2014. Google Scholar
  17. Hu Ding, Lunjia Hu, Lingxiao Huang, and Jian Li. Capacitated center problems with two-sided bounds and outliers. In Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS), pages 325-336, 2017. Google Scholar
  18. Hu Ding and Jinhui Xu. Solving the chromatic cone clustering problem via minimum spanning sphere. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pages 773-784, 2011. Google Scholar
  19. Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1471-1490, 2015. Google Scholar
  20. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating connected facility location with lower and upper bounds via LP rounding. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 1:1-1:14, 2016. Google Scholar
  21. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  22. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. Google Scholar
  23. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3):533-550, 1986. Google Scholar
  24. Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215, 1979. Google Scholar
  25. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 731-740, 2002. Google Scholar
  26. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  27. Samir Khuller, Robert Pless, and Yoram J. Sussmann. Fault tolerant k-center problems. Theoretical Computer Science, 242(1-2):237-245, 2000. Google Scholar
  28. Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM Journal on Discrete Mathematics, 13(3):403-418, 2000. Google Scholar
  29. Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146-188, 2000. Google Scholar
  30. Jian Li, Ke Yi, and Qin Zhang. Clustering with diversity. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), pages 188-200, 2010. Google Scholar
  31. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. Google Scholar
  32. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM Journal on Computing, 45(2):530-547, 2016. Google Scholar
  33. Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. CoRR, abs/1802.02497, 2018. URL: http://arxiv.org/abs/1802.02497.
  34. David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC), pages 265-274, 1997. Google Scholar
  35. Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schrödl. Constrained k-means clustering with background knowledge. In Proceedings of the 18th International Conference on Machine Learning (ICML), pages 577-584, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact