Document Open Access Logo

Submodular Clustering in Low Dimensions

Authors Arturs Backurs, Sariel Har-Peled

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.8.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Arturs Backurs
  • Toyota Technological Institute at Chicago, Il, USA
Sariel Har-Peled
  • University of Illinois at Urbana-Champaign, Il, USA

Funding

  • Har-Peled, Sariel: Work on this paper was partially supported by a NSF AF awards CCF-1907400 and CCF-1421231.

Cite As Get BibTex

Arturs Backurs and Sariel Har-Peled. Submodular Clustering in Low Dimensions. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.8

Abstract

We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ ℝ^d, the goal is to pick k centers C ⊆ ℝ^d that maximize the service ∑_{p∈P}φ(𝖽(p,C)) to the points P, where 𝖽(p,C) is the distance of p to its nearest center in C, and φ is a non-increasing service function φ: ℝ+ → ℝ+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients - indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an n^{ε^-O(d)} time algorithm for this problem that achieves a (1-ε)-approximation. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function φ: ℝ+ → ℝ+.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
  • Theory of computation → Computational geometry
Keywords
  • clustering
  • covering
  • PTAS

Metrics

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

References

  1. Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis. Efficient density evaluation for smooth kernels. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 615-626. IEEE, 2018. Google Scholar
  2. Vijay V. S. P. Bhattiprolu and Sariel Har-Peled. Separating a Voronoi diagram via local search. In Sándor P. Fekete and Anna Lubiw, editors, Proc. 32nd Int. Annu. Sympos. Comput. Geom. (SoCG), volume 51 of LIPIcs, pages 18:1-18:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.18.
  3. Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation schemes for geometric coverage problems. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, Proc. 27th Annu. Euro. Sympos. Alg. (ESA), volume 112 of LIPIcs, pages 17:1-17:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.17.
  4. Moses Charikar and Paris Siminelakis. Hashing-based-estimators for kernel density in high dimensions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 1032-1043. IEEE, 2017. Google Scholar
  5. Vincent Cohen-Addad. A fast approximation scheme for low-dimensional k-means. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 430-440. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  6. Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019. Google Scholar
  7. 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. SIAM J. Comput., 48(2):644-667, 2019. URL: https://doi.org/10.1137/17M112717X.
  8. Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 329-343. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.329.
  9. M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Santa Clara, CA, USA, 3rd edition, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
  10. R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley-Interscience, New York, 2nd edition, 2001. Google Scholar
  11. Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R Salavatipour. Approximation schemes for clustering with outliers. ACM Transactions on Algorithms (TALG), 15(2):26, 2019. Google Scholar
  12. Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour. Local search yields a PTAS for k-means in doubling metrics. SIAM Journal on Computing, 48(2):452-480, 2019. Google Scholar
  13. Bogdan Georgescu, Ilan Shimshoni, and Peter Meer. Mean shift based clustering in high dimensions: A texture classification example. In ICCV, volume 3, page 456, 2003. Google Scholar
  14. Leslie Greengard and John Strain. The fast gauss transform. SIAM Journal on Scientific and Statistical Computing, 12(1):79-94, 1991. Google Scholar
  15. Kai Jin, Jian Li, Haitao Wang, Bowei Zhang, and Ningye Zhang. Near-linear time approximation schemes for geometric maximum coverage. Theoretical Computer Science, 725:64-78, 2018. URL: https://doi.org/10.1016/j.tcs.2017.11.026.
  16. Kiyohito Nagano, Yoshinobu Kawahara, and Satoru Iwata. Minimum average cost clustering. In John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, Neural Info. Proc. Sys. (NIPS), pages 1759-1767. Curran Associates, Inc., 2010. URL: http://papers.nips.cc/paper/4106-minimum-average-cost-clustering.
  17. Kai Wei, Rishabh K. Iyer, Shengjie Wang, Wenruo Bai, and Jeff A. Bilmes. Mixed robust/average submodular partitioning: Fast algorithms, guarantees, and applications. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Neural Info. Proc. Sys. (NIPS), pages 2233-2241, 2015. URL: http://papers.nips.cc/paper/5706-mixed-robustaverage-submodular-partitioning-fast-algorithms-guarantees-and-applications.
  18. L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982. URL: https://doi.org/10.1007/BF02579435.
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