Non-Uniform k-Center and Greedy Clustering
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/3054287/LIPIcs-SWAT-2022-28.pdf.jpg?sequence=6&isAllowed=y)
Åpne
Permanent lenke
https://hdl.handle.net/11250/3054287Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
- Department of Informatics [978]
- Registrations from Cristin [10237]
Originalversjon
Leibniz International Proceedings in Informatics. 2022, 227, 28:1-28:20. https://doi.org/10.4230/LIPIcs.SWAT.2022.28Sammendrag
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.