Non-Uniform $k$-Center and Greedy Clustering

Tanmay Inamdar; Kasturi Varadarajan

doi:10.48550/arxiv.2111.06362

Back

Non-Uniform $k$-Center and Greedy Clustering

Preprint

Open access

Non-Uniform $k$-Center and Greedy Clustering

Tanmay Inamdar and Kasturi Varadarajan

ArXiv.org

11/11/2021

DOI: 10.48550/arxiv.2111.06362

Files and links (1)

url

https://doi.org/10.48550/arXiv.2111.06362View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

In the Non-Uniform $k$-Center 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$-NU$k$C Problem, 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 \le i \le 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$-NU$k$C is not possible if $t$ is unbounded. 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$-NU$k$C 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$-NU$k$C is known via the results of Chakrabarty and Negahbani [IPCO 2021], and Jia et al. [To appear in 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$-NU$k$C problem, eventually bringing us closer to the resolution of the CGK conjecture.

Details

Title: Subtitle: Non-Uniform $k$-Center and Greedy Clustering
Creators: Tanmay Inamdar
Kasturi Varadarajan
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2111.06362
ISSN: 2331-8422
Language: English
Date posted: 11/11/2021
Academic Unit: Computer Science
Record Identifier: 9984411097702771

Metrics

5 Record Views