On Perturbation Resilience of Non-Uniform k-Center

Author Sayan Bandyapadhyay



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.31.pdf
  • Filesize: 0.62 MB
  • 22 pages

Document Identifiers

Author Details

Sayan Bandyapadhyay
  • Department of Informatics, University of Bergen, Norway

Acknowledgements

I am indebted to Kasturi Varadarajan and Tanmay Inamdar for several helpful discussions and for giving invaluable feedback on this work. I also thank the anonymous reviewers whose suggestions have helped to further improve the quality of the paper.

Cite AsGet BibTex

Sayan Bandyapadhyay. On Perturbation Resilience of Non-Uniform k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.31

Abstract

The Non-Uniform k-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical k-center clustering problem. In NUkC, given a set of n points P in a metric space and non-negative numbers r₁, r₂, … , r_k, the goal is to find the minimum dilation α and to choose k balls centered at the points of P with radius α⋅ r_i for 1 ≤ i ≤ k, such that all points of P are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a "bi-criteria" constant approximation algorithm that uses a constant times k balls. Surprisingly, no true approximation is known even in the special case when the r_i’s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the r_i’s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any "good" approximation for the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Approximation algorithms
Keywords
  • Non-Uniform k-center
  • stability
  • clustering
  • perturbation resilience

Metrics

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

References

  1. David Adjiashvili, Andrea Baggio, and Rico Zenklusen. Firefighting on trees beyond integrality gaps. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, pages 2364-2383, 2017. Google Scholar
  2. Manu Agarwal, Ragesh Jaiswal, and Arindam Pal. k-means++ under approximation stability. Theor. Comput. Sci., 588:37-51, 2015. Google Scholar
  3. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, pages 61-72, 2017. Google Scholar
  4. Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilient problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, pages 438-451, 2017. Google Scholar
  5. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields a PTAS for k-median and k-means clustering. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 309-318, 2010. Google Scholar
  6. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inf. Process. Lett., 112(1-2):49-54, 2012. Google Scholar
  7. Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-center clustering under perturbation resilience. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, pages 68:1-68:14, 2016. Google Scholar
  8. Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. SIAM J. Comput., 45(1):102-155, 2016. Google Scholar
  9. Sayan Bandyapadhyay and Kasturi R. Varadarajan. Approximate clustering via metric partitioning. In 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Australia, pages 15:1-15:13, 2016. Google Scholar
  10. Yonatan Bilu and Nathan Linial. Are stable instances easy? Combinatorics, Probability & Computing, 21(5):643-660, 2012. Google Scholar
  11. Valentin Bura. A kernel method for positive 1-in-3-sat. CoRR, abs/1808.02821, 2018. URL: http://arxiv.org/abs/1808.02821.
  12. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1-23:31, 2017. Google Scholar
  13. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, pages 67:1-67:15, 2016. Google Scholar
  14. Chandra Chekuri and Shalmoli Gupta. Perturbation resilient clustering for k-center and related problems via LP relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018 - Princeton, NJ, USA, pages 9:1-9:16, 2018. Google Scholar
  15. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Joseph Naor. Asymmetric k-center is log^*n-hard to approximate. J. ACM, 52(4):538-551, 2005. Google Scholar
  16. Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 2017, pages 49-60, 2017. Google Scholar
  17. Amit Deshpande, Anand Louis, and Apoorv Singh. On euclidean k-means clustering with alpha-center proximity. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 2087-2095. PMLR, 16-18 apr 2019. Google Scholar
  18. Stephen Finbow, Andrew D. King, Gary MacGillivray, and Romeo Rizzi. The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307(16):2094-2105, 2007. Google Scholar
  19. Zachary Friggstad, Kamyar Khodamoradi, and Mohammad R. Salavatipour. Exact algorithms and lower bounds for stable instances of euclidean k-means. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2958-2972, 2019. Google Scholar
  20. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-306, 1985. Google Scholar
  21. Anupam Gupta. Embedding tree metrics into low-dimensional euclidean spaces. Discrete & Computational Geometry, 24(1):105-116, 2000. Google Scholar
  22. Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10(2):180-184, 1985. Google Scholar
  23. Andrew D. King and Gary MacGillivray. The firefighter problem for cubic graphs. Discrete Mathematics, 310(3):614-621, 2010. Google Scholar
  24. Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, pages 299-308, 2010. Google Scholar
  25. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-Linial stable instances of max cut and minimum multiway cut. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, pages 890-906, 2014. Google Scholar
  26. Matús Mihalák, Marcel Schöngens, Rastislav Srámek, and Peter Widmayer. On the complexity of the metric TSP under stability considerations. In Proceedings of 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011: Theory and Practice of Computer Science, Nový Smokovec, Slovakia., pages 382-393, 2011. Google Scholar
  27. Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. The effectiveness of Lloyd-type methods for the k-means problem. J. ACM, 59(6):28:1-28:22, 2012. Google Scholar
  28. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 1978, San Diego, California, USA, pages 216-226. ACM, 1978. Google Scholar
  29. Leslie G Valiant and Vijay V Vazirani. NP is as easy as detecting unique solutions. In Proceedings of the 17th Annual ACM Symposium on Theory of computing, STOC 1985, pages 458-463. ACM, 1985. 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