Inamdar, Tanmay ;
Varadarajan, Kasturi
NonUniform kCenter and Greedy Clustering
Abstract
In the NonUniform kCenter (NUkC) problem, a generalization of the famous kcenter 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 tNUkC, 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:146:19], who showed that a constant approximation for tNUkC 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 tNUkC 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 3NUkC 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 NonUniform kCenter for 4 distinct types of radii. Our result is obtained via a novel combination of tools and techniques from the kcenter literature, which also demonstrates that the different generalizations of kcenter involving nonuniform radii, and multiple coverage constraints (i.e., colorful kcenter), are closely interlinked with each other. We hope that our ideas will contribute towards a deeper understanding of the tNUkC problem, eventually bringing us closer to the resolution of the CGK conjecture.
BibTeX  Entry
@InProceedings{inamdar_et_al:LIPIcs.SWAT.2022.28,
author = {Inamdar, Tanmay and Varadarajan, Kasturi},
title = {{NonUniform kCenter and Greedy Clustering}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {28:128:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16188},
URN = {urn:nbn:de:0030drops161881},
doi = {10.4230/LIPIcs.SWAT.2022.28},
annote = {Keywords: kcenter, approximation algorithms, nonuniform kcenter, clustering}
}
22.06.2022
Keywords: 

kcenter, approximation algorithms, nonuniform kcenter, clustering 
Seminar: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Issue date: 

2022 
Date of publication: 

22.06.2022 