Privacy preserving clustering with constraints. (English) Zbl 1499.90117
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 96, 14 p. (2018).
Summary: 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 \(\ell\) clients will be assigned to it. We show how to combine privacy with several other constraints.
For the entire collection see [Zbl 1392.68012].
For the entire collection see [Zbl 1392.68012].
MSC:
| 90B80 | Discrete location and assignment |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
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. {\it Mathematical Programming}, 141(1-2):527-547, 2013. · Zbl 1274.90191 |
| [2] | Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu. Approximation algorithms for k-anonymity. In {\it Proceedings} {\it 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. {\it ACM Transaction on} {\it Algorithms}, 6(3):49:1-49:19, 2010. · Zbl 1300.68023 |
| [4] | Sara Ahmadian and Chaitanya Swamy. Approximation algorithms for clustering problems with lower bounds and outliers. In {\it 43rd International Colloquium on Automata, Languages,} {\it and Programming, (ICALP)}, pages 69:1-69:15, 2016. · Zbl 1395.90172 |
| [5] | Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. {\it Mathematical Programming}, 154(1-2):29-53, 2015. · Zbl 1337.90036 |
| [6] | Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. {\it SIAM} {\it Journal on Computing}, 33(3):544-562, 2004. · Zbl 1105.68118 |
| [7] | Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In {\it 20th Annual European Symposium on Algorithms (ESA)}, pages 133- 144, 2012. · Zbl 1365.90159 |
| [8] | Judit Bar-Ilan, Guy Kortsarz, and David Peleg. How to allocate network centers. {\it Journal} {\it of Algorithms}, 15(3):385-415, 1993. · Zbl 0784.68012 |
| [9] | Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for {\it k}-median and positive correlation in budgeted optimization. {\it ACM Transactions on Algorithms}, 13(2):23:1-23:31, 2017. · Zbl 1454.90069 |
| [10] | Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform {\it k}-center problem. In {\it Proceedings of the 43rd International Colloquium on Automata, Lan-} {\it guages, and Programming (ICALP)}, volume 55 of {\it LIPIcs. Leibniz Int. Proc. Inform.}, pages Art. No. 67, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. · Zbl 1388.68303 |
| [11] | Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem.{\it Journal of Computer and System} {\it Sciences}, 65(1):129-149, 2002. · Zbl 1023.90037 |
| [12] | Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In {\it Proceedings of the 12th Annual Symposium on} {\it Discrete Algorithms (SODA)}, pages 642-651, 2001. · Zbl 1012.90026 |
| [13] | Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. {\it Algorithmica}, 75(1):27-52, 2016. · Zbl 1344.68282 |
| [14] | Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In {\it Advances in Neural Information Processing Systems 30: Annual Con-} {\it ference on Neural Information Processing Systems 2017 (NIPS)}, pages 5036-5044, 2017. |
| [15] | Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In {\it 53rd Annual IEEE Symposium on Foundations of} {\it Computer Science (FOCS)}, pages 273-282, 2012. |
| [16] | Marek Cygan and Tomasz Kociumaka. Constant factor approximation for capacitated kcenter with outliers. In {\it Proceedings of the 31st International Symposium on Theoretical} {\it Aspects of Computer Science (STACS)}, pages 251-262, 2014. · Zbl 1359.90056 |
| [17] | Hu Ding, Lunjia Hu, Lingxiao Huang, and Jian Li. Capacitated center problems with two-sided bounds and outliers. In {\it Proceedings of the 15th International Symposium on} {\it Algorithms and Data Structures (WADS)}, pages 325-336, 2017. · Zbl 1454.68179 |
| [18] | Hu Ding and Jinhui Xu. Solving the chromatic cone clustering problem via minimum spanning sphere. In {\it Proceedings of the 38th International Colloquium on Automata, Languages} {\it and Programming (ICALP)}, pages 773-784, 2011. · Zbl 1333.68292 |
| [19] | Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. In {\it Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on} {\it Discrete Algorithms (SODA)}, pages 1471-1490, 2015. · Zbl 1371.68291 |
| [20] | Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating connected facility location with lower and upper bounds via LP rounding. In {\it 15th Scandi-} {\it navian Symposium and Workshops on Algorithm Theory (SWAT)}, pages 1:1-1:14, 2016. · Zbl 1378.68195 |
| [21] | Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. {\it Theoretical} {\it Computer Science}, 38:293-306, 1985. · Zbl 0567.62048 |
| [22] | Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. {\it Journal of Algorithms}, 31(1):228-248, 1999. · Zbl 0928.68137 |
| [23] | Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. {\it Journal of the ACM}, 33(3):533-550, 1986. |
| [24] | Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. {\it Discrete Applied Mathematics}, 1(3):209-215, 1979. · Zbl 0424.90049 |
| [25] | Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems.In {\it Proceedings of the 34th Annual ACM Symposium on Theory of} {\it Computing (STOC)}, pages 731-740, 2002. · Zbl 1192.90106 |
| [26] | Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and {\it k}-median problems using the primal-dual schema and lagrangian relaxation. {\it Journal} {\it of the ACM}, 48(2):274-296, 2001. · Zbl 1138.90417 |
| [27] | Samir Khuller, Robert Pless, and Yoram J. Sussmann. Fault tolerant k-center problems. {\it Theoretical Computer Science}, 242(1-2):237-245, 2000. · Zbl 0944.68141 |
| [28] | Samir Khuller and Yoram J. Sussmann. The capacitated {\it K }-center problem. {\it SIAM Journal} {\it on Discrete Mathematics}, 13(3):403-418, 2000. · Zbl 0947.05073 |
| [29] | Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. {\it Journal of Algorithms}, 37(1):146-188, 2000. · Zbl 0962.68044 |
| [30] | Jian Li, Ke Yi, and Qin Zhang. Clustering with diversity. In {\it Proceedings of the 37th} {\it International Colloquium on Automata, Languages and Programming (ICALP)}, pages 188- 200, 2010. · Zbl 1287.68182 |
| [31] | Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. {\it Information and Computation}, 222:45-58, 2013. · Zbl 1281.68236 |
| [32] | Shi Li and Ola Svensson.Approximating k-median via pseudo-approximation.{\it SIAM} {\it Journal on Computing}, 45(2):530-547, 2016. · Zbl 1338.90346 |
| [33] | Clemens Rösner and Melanie Schmidt.Privacy preserving clustering with constraints. {\it CoRR}, abs/1802.02497, 2018. arXiv:1802.02497. |
| [34] | David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In {\it Proceedings of the Twenty-Ninth Annual ACM Symposium on the} {\it Theory of Computing (STOC)}, pages 265-274, 1997. · Zbl 0962.68008 |
| [35] | Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schrödl. Constrained k-means clustering with background knowledge. In {\it Proceedings of the 18th International Conference on} {\it Machine Learning (ICML)}, pages 577-584, 2001. |
| [36] | :14 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
