Document Open Access Logo

Revisiting Priority k-Center: Fairness and Outliers

Authors Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.21.pdf
  • Filesize: 0.8 MB
  • 20 pages

Document Identifiers

Author Details

Tanvi Bajpai
  • University of Illinois, Urbana-Champaign, Urbana, IL, USA
Deeparnab Chakrabarty
  • Dartmouth College, Hanover, NH, USA
Chandra Chekuri
  • University of Illinois, Urbana-Champaign, Urbana, IL, USA
Maryam Negahbani
  • Dartmouth College, Hanover, NH, USA

Funding

  • Bajpai, Tanvi: Supported in part by NSF grant CCF-1910149.
  • Chakrabarty, Deeparnab: Supported by NSF grants CCF-1813053 and CCF-2041920.
  • Chekuri, Chandra: Supported by NSF grants CCF-1910149 and CCF-1907939.

Cite AsGet BibTex

Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting Priority k-Center: Fairness and Outliers. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.21

Abstract

In the Priority k-Center problem, the input consists of a metric space (X,d), an integer k and for each point v ∈ X a priority radius r(v). The goal is to choose k-centers S ⊆ X to minimize max_{v ∈ X} 1/(r(v)) d(v,S). If all r(v)’s were uniform, one obtains the classical k-center problem. Plesník [Ján Plesník, 1987] introduced this problem and gave a 2-approximation algorithm matching the best possible algorithm for vanilla k-center. We show how the Priority k-Center problem is related to two different notions of fair clustering [Harris et al., 2019; Christopher Jung et al., 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority k-Center with outliers. Our framework extends to generalizations of Priority k-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Fairness
  • Clustering
  • Approximation
  • Outliers

Metrics

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

Related Versions

References

  1. Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. In Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 52-65, 2020. Google Scholar
  2. Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting priority k-center: Fairness and outliers, 2021. URL: http://arxiv.org/abs/2103.03337.
  3. Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi R. Varadarajan. A constant approximation for colorful k-center. In Proceedings, European Symposium on Algorithms (ESA), pages 12:1-12:14, 2019. Google Scholar
  4. Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Adv. in Neural Information Processing Systems (NeurIPS), pages 4955-4966, 2019. Google Scholar
  5. Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 18:1-18:22, 2019. Google Scholar
  6. Robert D. Carr and Santosh S. Vempala. Randomized metarounding. Random Struct. Algorithms, 20(3):343-352, 2002. Preliminary version in STOC 2000. Google Scholar
  7. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. ACM Transactions on Algorithms (TALG), 16(4):1-19, 2020. Preliminary version in ICALP, 2016. Google Scholar
  8. Deeparnab Chakrabarty and Maryam Negahbani. Generalized center problems with outliers. ACM Transactions on Algorithms (TALG), 15(3):1-14, 2019. Preliminary version in ICALP 2018. Google Scholar
  9. T-H Hubert Chan, Michael Dinitz, and Anupam Gupta. Spanners with slack. In Proceedings, European Symposium on Algorithms (ESA), pages 196-207, 2006. Google Scholar
  10. Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 642-651, 2001. Google Scholar
  11. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Local global tradeoffs in metric embeddings. SIAM Journal on Computing (SICOMP), 39(6):2487-2512, 2010. Google Scholar
  12. Chandra Chekuri and Shalmoli Gupta. Perturbation resilient clustering for k-center and related problems via LP relaxations. In Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 9:1-9:16, 2018. Google Scholar
  13. Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath. Multicommodity flows and cuts in polymatroidal networks. SIAM Journal on Computing, 44(4):912-943, 2015. Preliminary version in ITCS 2012. Google Scholar
  14. Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27-52, 2016. Google Scholar
  15. Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Proceedings, International Conference on Machine Leanring (ICML), volume 97, pages 1032-1041, 2019. Google Scholar
  16. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Adv. in Neural Information Processing Systems (NeurIPS), pages 5029-5037, 2017. Google Scholar
  17. Jack Edmonds and Rick Giles. A min-max relation for submodular functions on graphs. Annals of Discrete Mathematics, 1:185-204, 1977. Google Scholar
  18. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979. Google Scholar
  19. Teofilo F. Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  20. Inge Li Gørtz and Anthony Wirth. Asymmetry in k-center variants. Theoretical Computer Science, 361(2-3):188-199, 2006. Preliminary version in APPROX 2003. Google Scholar
  21. Anupam Gupta, Guru Guruganesh, and Melanie Schmidt. Approximation algorithms for aversion k-clustering via local k-median. In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), 2016. Google Scholar
  22. David G. Harris, Shi Li, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. Approximation algorithms for stochastic clustering. Journal of Machine Learning Research, 20(153):1-33, 2019. Preliminary version in NeurIPS 2018. Google Scholar
  23. David G Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. A lottery model for center-type problems with outliers. ACM Transactions on Algorithms (TALG), 2019. Preliminary version in APPROX 2017. Google Scholar
  24. Refael Hassin. Minimum cost flow with set-constraints. Networks, 12(1):1-21, 1982. Google Scholar
  25. Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 1985. Google Scholar
  26. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533-550, 1986. Google Scholar
  27. Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorful k-center clustering. In Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 209-222, 2020. Google Scholar
  28. Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In Proceedings, Foundations of Responsible Computing, FORC 2020, volume 156, pages 5:1-5:15, 2020. Google Scholar
  29. Eugene L Lawler and Charles U Martel. Computing maximal “polymatroidal” network flows. Mathematics of Operations Research, 7(3):334-347, 1982. Google Scholar
  30. Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In International Conference on Machine Learning, pages 6586-6596. PMLR, 2020. Google Scholar
  31. Evi Micha and Nisarg Shah. Proportionally Fair Clustering Revisited. Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), 2020. Google Scholar
  32. Ján Plesník. A heuristic for the p-center problems in graphs. Discrete Applied Mathematics, 17(3):263-268, 1987. Google Scholar
  33. Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), volume 107, pages 96:1-96:14, 2018. 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