LIPIcs.SWAT.2022.28.pdf
- Filesize: 0.88 MB
- 20 pages
Document
Non-Uniform k-Center and Greedy Clustering
Authors
Tanmay Inamdar 
,
-
Part of:
Volume:
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-22
File
Document Identifiers
Author Details
Cite As Get BibTex
Tanmay Inamdar and Kasturi Varadarajan. Non-Uniform k-Center and Greedy Clustering. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.28
Abstract
In the Non-Uniform k-Center (NUkC) problem, a generalization of the famous k-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In t-NUkC, we assume that the number of distinct radii is equal to t, and we are allowed to use k_i balls of radius r_i, for 1 ≤ i ≤ t. This problem was introduced by Chakrabarty et al. [ACM Trans. Alg. 16(4):46:1-46:19], who showed that a constant approximation for t-NUkC is not possible if t is unbounded, assuming 𝖯 ≠ NP. On the other hand, they gave a bicriteria approximation that violates the number of allowed balls as well as the given radii by a constant factor. They also conjectured that a constant approximation for t-NUkC should be possible if t is a fixed constant. Since then, there has been steady progress towards resolving this conjecture - currently, a constant approximation for 3-NUkC is known via the results of Chakrabarty and Negahbani [IPCO 2021], and Jia et al. [SOSA 2022]. We push the horizon by giving an O(1)-approximation for the Non-Uniform k-Center for 4 distinct types of radii. Our result is obtained via a novel combination of tools and techniques from the k-center literature, which also demonstrates that the different generalizations of k-center involving non-uniform radii, and multiple coverage constraints (i.e., colorful k-center), are closely interlinked with each other. We hope that our ideas will contribute towards a deeper understanding of the t-NUkC problem, eventually bringing us closer to the resolution of the CGK conjecture.
Subject Classification
ACM Subject Classification
- Theory of computation → Facility location and clustering
- Theory of computation → Rounding techniques
Keywords
- k-center
- approximation algorithms
- non-uniform k-center
- clustering
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. In Daniel Bienstock and Giacomo Zambelli, editors, Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, London, UK, June 8-10, 2020, Proceedings, volume 12125 of Lecture Notes in Computer Science, pages 52-65. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45771-6_5.
- Sayan Bandyapadhyay. On perturbation resilience of non-uniform k-center. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 31:1-31:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.31.
- Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi R. Varadarajan. A constant approximation for colorful k-center. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 12:1-12:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.12.
- Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. ACM Trans. Algorithms, 16(4):46:1-46:19, 2020. URL: https://doi.org/10.1145/3392720.
-
Deeparnab Chakrabarty and Maryam Negahbani. Generalized center problems with outliers. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
- Deeparnab Chakrabarty and Maryam Negahbani. Robust k-center with two types of radii. In Mohit Singh and David P. Williamson, editors, Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings, volume 12707 of Lecture Notes in Computer Science, pages 268-282. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-73879-2_19.
-
Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 642-651. Society for Industrial and Applied Mathematics, 2001.
-
David G Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. A lottery model for center-type problems with outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
-
Dorit S Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and vlsi. Journal of the ACM (JACM), 32(1):130-136, 1985.
-
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.
-
Tanmay Inamdar and Kasturi Varadarajan. Capacitated sum-of-radii clustering: An fpt approximation. In 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
- Xinrui Jia, Lars Rohwedder, Kshiteej Sheth, and Ola Svensson. Towards non-uniform k-center with constant types of radii. In Karl Bringmann and Timothy Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, pages 228-237. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977066.16.
- Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorful k-center clustering. In Daniel Bienstock and Giacomo Zambelli, editors, Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, London, UK, June 8-10, 2020, Proceedings, volume 12125 of Lecture Notes in Computer Science, pages 209-222. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45771-6_17.