Document Open Access Logo

Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations

Authors Chandra Chekuri, Shalmoli Gupta

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.9.pdf
  • Filesize: 0.8 MB
  • 16 pages

Document Identifiers

Author Details

Chandra Chekuri
  • Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801, USA
Shalmoli Gupta
  • Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801, USA

Funding

Work on this paper supported in part by NSF grants CCF-1319376 and CCF-1526799.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.9

Abstract

We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [Yonatan Bilu and Nathan Linial, 2010] and Awasthi, Blum and Sheffet [Awasthi et al., 2012]. A clustering instance I is said to be alpha-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of alpha and the perturbed distances satisfy the metric property - this is the metric perturbation resilience property introduced in [Angelidakis et al., 2017] and a weaker requirement than prior models. We make two high-level contributions. 
- We show that the natural LP relaxation of k-center and asymmetric k-center is integral for 2-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results [Maria{-}Florina Balcan et al., 2016; Angelidakis et al., 2017] that are based on new algorithms designed for the perturbation model. 
- We define a simple new model of perturbation resilience for clustering with outliers. Using this model we show that the unified MST and dynamic programming based algorithm proposed in [Angelidakis et al., 2017] exactly solves the clustering with outliers problem for several common center based objectives (like k-center, k-means, k-median) when the instances is 2-perturbation resilient. We further show that a natural LP relxation is integral for 2-perturbation resilient instances of k-center with outliers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Clustering
  • Perturbation Resilience
  • LP Integrality
  • Outliers
  • Beyond Worst Case Analysis

Metrics

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

Related Versions

References

  1. Charu C. Aggarwal. Outlier Analysis. Springer Publishing Company, Incorporated, 2013. Google Scholar
  2. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. In FOCS, pages 61-72, 2017. Google Scholar
  3. Sara Ahmadian and Chaitanya Swamy. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. In ICALP, pages 69:1-69:15, 2016. Google Scholar
  4. Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resilient problems. In STOC, pages 438-451, 2017. Google Scholar
  5. Aaron Archer. Two O(log^* K)-approximation algorithms for the asymmetric k-center problem. In IPCO, pages 1-14, 2001. Google Scholar
  6. David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In SODA, pages 1027-1035, 2007. Google Scholar
  7. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields a ptas for k-median and k-means clustering. In FOCS, pages 309-318, 2010. Google Scholar
  8. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inf. Process. Lett., 112(1-2):49-54, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2011.10.006.
  9. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. CoRR, abs/1502.03316, 2015. URL: http://arxiv.org/abs/1502.03316.
  10. Pranjal Awasthi and Or Sheffet. Improved spectral-norm bounds for clustering. In APPROX-RANDOM, pages 37-49, 2012. Google Scholar
  11. Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Approximate clustering without the approximation. In SODA, pages 1068-1077, 2009. Google Scholar
  12. Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-center clustering under perturbation resilience. In ICALP, pages 68:1-68:14, 2016. Google Scholar
  13. Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. In ICALP, pages 63-74, 2012. Google Scholar
  14. Maria-Florina Balcan and Colin White. Clustering under local stability: Bridging the gap between worst-case and beyond worst-case analysis. CoRR, abs/1705.07157, 2017. URL: http://arxiv.org/abs/1705.07157.
  15. Yonatan Bilu, Amit Daniely, Nati Linial, and Michael E. Saks. On the practically interesting instances of MAXCUT. In STACS, pages 526-537, 2013. Google Scholar
  16. Yonatan Bilu and Nathan Linial. Are stable instances easy? In ICS, pages 332-341, 2010. Google Scholar
  17. Johannes Blömer, Christiane Lammersen, Melanie Schmidt, and Christian Sohler. Theoretical analysis of the dollarkdollar-means algorithm - A survey. CoRR, abs/1602.08254, 2016. URL: http://arxiv.org/abs/1602.08254.
  18. 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. URL: http://dx.doi.org/10.1145/2981561.
  19. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In ICALP, pages 67:1-67:15, 2016. Google Scholar
  20. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. In STOC, pages 1-10, 1999. Google Scholar
  21. Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In SODA, pages 642-651, 2001. Google Scholar
  22. Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. In SODA, pages 826-835, 2008. Google Scholar
  23. 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. J. ACM, 52(4):538-551, 2005. URL: http://dx.doi.org/10.1145/1082036.1082038.
  24. Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In FOCS, pages 49-60, 2017. Google Scholar
  25. T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-306, 1985. Google Scholar
  26. D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180-184, 1985. Google Scholar
  27. K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. J. ACM, 50(6):795-824, 2003. URL: http://dx.doi.org/10.1145/950620.950621.
  28. Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. CoRR, abs/1711.01323, 2017. URL: http://arxiv.org/abs/1711.01323.
  29. Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In FOCS, pages 299-308, 2010. Google Scholar
  30. S. Lloyd. Least squares quantization in pcm. IEEE Trans. Inf. Theor., 28(2):129-137, 2006. URL: http://dx.doi.org/10.1109/TIT.1982.1056489.
  31. Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu-linial stable instances of max cut and minimum multiway cut. In SODA, pages 890-906. SIAM, 2014. Google Scholar
  32. Matús Mihalák, Marcel Schöngens, Rastislav Srámek, and Peter Widmayer. On the complexity of the metric TSP under stability considerations. In SOFSEM, pages 382-393, 2011. Google Scholar
  33. Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. The effectiveness of lloyd-type methods for the k-means problem. In FOCS, pages 165-176, 2006. Google Scholar
  34. Rina Panigrahy and Sundar Vishwanathan. An O(log^* n) approximation algorithm for the asymmetric p-center problem. J. Algorithms, 27(2):259-268, 1998. URL: http://dx.doi.org/10.1006/jagm.1997.0921.
  35. Aravindan Vijayaraghavan, Abhratanu Dutta, and Alex Wang. Clustering stable instances of euclidean k-means. In NIPS, pages 6503-6512, 2017. 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 About DROPS Imprint Privacy Contact