License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.7
URN: urn:nbn:de:0030-drops-169458
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16945/
Anegg, Georg ;
Vargas Koch, Laura ;
Zenklusen, Rico
Techniques for Generalized Colorful k-Center Problems
Abstract
Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. This is a natural generalization of the robust (or outlier) setting, which has been studied extensively and is amenable to a variety of classic algorithmic techniques. In contrast, for the case of multiple covering constraints (the so-called colorful setting), specialized techniques have only been developed recently for k-Center clustering variants, which is also the focus of this paper.
While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this paper, we present a quite versatile framework to deal with various constraints on the facilities in the colorful setting, by combining ideas from the iterative greedy procedure for Colorful k-Center by Inamdar and Varadarajan with new ingredients. To exemplify our framework, we show how it leads, for a constant number γ of colors, to the first constant-factor approximations for both Colorful Matroid Supplier with respect to a linear matroid and Colorful Knapsack Supplier. In both cases, we readily get an O(2^γ)-approximation.
Moreover, for Colorful Knapsack Supplier, we show that it is possible to obtain constant approximation guarantees that are independent of the number of colors γ, as long as γ = O(1), which is needed to obtain a polynomial running time. More precisely, we obtain a 7-approximation by extending a technique recently introduced by Jia, Sheth, and Svensson for Colorful k-Center.
BibTeX - Entry
@InProceedings{anegg_et_al:LIPIcs.ESA.2022.7,
author = {Anegg, Georg and Vargas Koch, Laura and Zenklusen, Rico},
title = {{Techniques for Generalized Colorful k-Center Problems}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {7:1--7:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16945},
URN = {urn:nbn:de:0030-drops-169458},
doi = {10.4230/LIPIcs.ESA.2022.7},
annote = {Keywords: Approximation Algorithms, Fair Clustering, Colorful k-Center}
}
|
Keywords: |
|
Approximation Algorithms, Fair Clustering, Colorful k-Center |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
