Document Open Access Logo

Approximate Clustering via Metric Partitioning

Authors Sayan Bandyapadhyay, Kasturi Varadarajan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.15.pdf
  • Filesize: 485 kB
  • 13 pages

Document Identifiers

Author Details

Sayan Bandyapadhyay
Kasturi Varadarajan

Cite AsGet BibTex

Sayan Bandyapadhyay and Kasturi Varadarajan. Approximate Clustering via Metric Partitioning. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.15

Abstract

In this paper we consider two metric covering/clustering problems - Minimum Cost Covering Problem (MCC) and k-clustering. In the MCC problem, we are given two point sets X (clients) and Y (servers), and a metric on X cup Y. We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the alpha-th power of the radii of the balls. Here alpha geq 1 is a parameter of the problem (but not of a problem instance). MCC is closely related to the k-clustering problem. The main difference between k-clustering and MCC is that in k-clustering one needs to select k balls to cover the clients. For any eps > 0, we describe quasi-polynomial time (1 + eps) approximation algorithms for both of the problems. However, in case of k-clustering the algorithm uses (1 + eps)k balls. Prior to our work, a 3^alpha and a c^alpha approximation were achieved by polynomial-time algorithms for MCC and k-clustering, respectively, where c > 1 is an absolute constant. These two problems are thus interesting examples of metric covering/clustering problems that admit (1 + eps)-approximation (using (1 + eps)k balls in case of k-clustering), if one is willing to settle for quasi-polynomial time. In contrast, for the variant of MCC where alpha is part of the input, we show under standard assumptions that no polynomial time algorithm can achieve an approximation factor better than O(log |X|) for alpha geq log |X|.
Keywords
  • Approximation Algorithms
  • Clustering
  • Covering
  • Probabilistic Parti- tions

Metrics

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

References

  1. Ittai Abraham, Yair Bartal, and Ofer Neimany. Advances in metric embedding theory. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 271-286. ACM, 2006. Google Scholar
  2. Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, and Kim Whittlesey. Minimum-cost coverage of point sets by disks. In Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006, pages 449-458, 2006. URL: http://dx.doi.org/10.1145/1137856.1137922.
  3. Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC'98, pages 106-113, New York, NY, USA, 1998. ACM. URL: http://dx.doi.org/10.1145/276698.276718.
  4. Sayan Bandyapadhyay and Kasturi R. Varadarajan. Approximate clustering via metric partitioning. CoRR, abs/1507.02222, 2015. URL: http://arxiv.org/abs/1507.02222.
  5. Sayan Bandyapadhyay and Kasturi R. Varadarajan. On variants of k-means clustering. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 14:1-14:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.14.
  6. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS'96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193. IEEE Computer Society, 1996. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4141, URL: http://dx.doi.org/10.1109/SFCS.1996.548477.
  7. Yair Bartal. Graph decomposition lemmas and their role in metric embedding methods. In Algorithms-ESA 2004, pages 89-97. Springer, 2004. Google Scholar
  8. Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. In Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, pages 71-82, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31155-0_7.
  9. Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, pages 460-471, 2005. URL: http://dx.doi.org/10.1007/11561071_42.
  10. Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci., 68(2):417-441, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.07.014.
  11. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. In FOCS, to appear, 2016. Google Scholar
  12. Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, and Peter Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Nord. J. Comput., 7(3):185-203, 2000. Google Scholar
  13. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput., 34(6):1302-1323, 2005. URL: http://dx.doi.org/10.1137/S0097539702402676.
  14. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.04.011.
  15. Ari Freund and Dror Rawitz. Combinatorial interpretations of dual fitting and primal fitting. In Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, pages 137-150, 2003. URL: http://dx.doi.org/10.1007/978-3-540-24592-6_11.
  16. Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484-498, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9282-7.
  17. Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On clustering to minimize the sum of radii. SIAM J. Comput., 41(1):47-60, 2012. URL: http://dx.doi.org/10.1137/100798144.
  18. Sariel Har-Peled. Geometric approximation algorithms, 2011. Google Scholar
  19. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130-136, 1985. URL: http://dx.doi.org/10.1145/2455.214106.
  20. Lior Kamma, Robert Krauthgamer, and Huy L Nguyên. Cutting corners cheaply, or how to remove steiner points. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1040. SIAM, 2014. Google Scholar
  21. Viggo Kann. On the approximability of np-complete optimization problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992. URL: http://www.csc.kth.se/~viggo/papers/phdthesis.pdf.
  22. Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks, 47(4):489-501, 2005. URL: http://dx.doi.org/10.1016/j.comnet.2004.08.012.
  23. Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. URL: http://dx.doi.org/10.1016/j.cosrev.2007.05.001.
  24. Mohammad Salavatipour Zachary Friggstad, Mohsen Rezapour. Local search yields a ptas for k-means in doubling metrics. In FOCS, to appear, 2016. 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