Document Open Access Logo

k-Center Clustering Under Perturbation Resilience

Authors Maria-Florina Balcan, Nika Haghtalab, Colin White

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.68.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Maria-Florina Balcan
Nika Haghtalab
Colin White

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.68

Abstract

The k-center problem is a canonical and long-studied facility location and clustering problem with many applications in both its symmetric and asymmetric forms. Both versions of the problem have tight approximation factors on worst case instances: a 2-approximation for symmetric kcenter and an O(log*(k))-approximation for the asymmetric version. Therefore to improve on these ratios, one must go beyond the worst case.

In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric k-center problems under a very natural input stability (promise) condition called alpha-perturbation resilience [Bilu Linial, 2012], which states that the optimal solution does not change under any alpha-factor perturbation to the input distances. We show that by assuming 2-perturbation resilience, the exact solution for the asymmetric k-center problem can be found in polynomial time. To our knowledge, this is the first problem that is hard to approximate to any constant factor in the worst case, yet can be optimally solved in polynomial time under perturbation resilience for a constant value of alpha. Furthermore, we prove our result is tight by showing symmetric k-center under (2-epsilon)-perturbation resilience is hard unless NP=RP.

This is the first tight result for any problem under perturbation resilience, i.e., this is the first time the exact value of alpha for which the problem switches from being NP-hard to efficiently computable has been found.

Our results illustrate a surprising relationship between symmetric and asymmetric k-center instances under perturbation resilience. Unlike approximation ratio, for which symmetric k-center is easily solved to a factor of 2 but asymmetric k-center cannot be approximated to any constant factor, both symmetric and asymmetric k-center can be solved optimally under resilience
to 2-perturbations.

Subject Classification

Keywords
  • k-center
  • clustering
  • perturbation resilience

Metrics

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

References

  1. Aaron Archer. Two o (log* k)-approximation algorithms for the asymmetric k-center problem. In Integer Programming and Combinatorial Optimization, pages 1-14. Springer, 2001. Google Scholar
  2. Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models - going beyond SVD. In 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 1-10, 2012. Google Scholar
  3. Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, and Rachel Ward. Relax, no need to round: Integrality of clustering formulations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 191-200, 2015. URL: http://dx.doi.org/10.1145/2688073.2688116.
  4. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields a ptas for k-median and k-means clustering. In 51st Annual IEEE Symposium on Foundations of Computer Science, pages 309-318, 2010. Google Scholar
  5. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 112(1):49-54, 2012. Google Scholar
  6. Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Approximate clustering without the approximation. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1068-1077, 2009. Google Scholar
  7. Maria-Florina Balcan and Mark Braverman. Approximate nash equilibria under stability conditions. Technical report, 2010. Google Scholar
  8. Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. In Automata, Languages, and Programming, pages 63-74. Springer, 2012. Google Scholar
  9. Shalev Ben-David and Lev Reyzin. Data stability in clustering: A closer look. In Algorithmic Learning Theory, pages 184-198. Springer, 2012. Google Scholar
  10. Yonatan Bilu and Nathan Linial. Are stable instances easy? Combinatorics, Probability and Computing, 21(05):643-660, 2012. Google Scholar
  11. Fazli Can. Incremental clustering for dynamic information processing. ACM Transactions on Information Systems (TOIS), 11(2):143-164, 1993. Google Scholar
  12. Fazli Can and ND Drochak. Incremental clustering for dynamic document databases. In Proceedings of the 1990 Symposium on Applied Computing, pages 61-67, 1990. Google Scholar
  13. Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 626-635, 1997. Google Scholar
  14. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Joseph Seffi Naor. Asymmetric k-center is log* n-hard to approximate. Journal of the ACM (JACM), 52(4):538-551, 2005. Google Scholar
  15. Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM Journal on Computing, 34(5):1129-1146, 2005. Google Scholar
  16. Martin E Dyer and Alan M Frieze. A simple heuristic for the p-centre problem. Operations Research Letters, 3(6):285-288, 1985. Google Scholar
  17. Rishi Gupta, Tim Roughgarden, and C Seshadhri. Decompositions of triangle-dense graphs. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 471-482. ACM, 2014. Google Scholar
  18. Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 331-340, 2013. Google Scholar
  19. Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180-184, 1985. Google Scholar
  20. Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In 51st Annual IEEE Symposium on Foundations of Computer Science, pages 299-308, 2010. Google Scholar
  21. Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1+ ε)-approximation algorithm for geometric k-means clustering in any dimensions. In Proceedings-Annual Symposium on Foundations of Computer Science, pages 454-462. IEEE, 2004. Google Scholar
  22. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-linial stable instances of max cut and minimum multiway cut. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 890-906. SIAM, 2014. Google Scholar
  23. Matúš Mihalák, Marcel Schöngens, Rastislav Šrámek, and Peter Widmayer. On the complexity of the metric tsp under stability considerations. In SOFSEM 2011: Theory and Practice of Computer Science, pages 382-393. Springer, 2011. Google Scholar
  24. Tim Roughgarden. Beyond worst-case analysis, 2014. URL: http://theory.stanford.edu/~tim/f14/f14.html.
  25. Sundar Vishwanathan. An o(log*n) approximation algorithm for the asymmetric p-center problem. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-5, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.313861.
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 About DROPS Imprint Privacy Contact