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.ISAAC.2021.41
URN: urn:nbn:de:0030-drops-154740
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15474/
Eskandari, Marzieh ;
Khare, Bhavika ;
Kumar, Nirman
Separated Red Blue Center Clustering
Abstract
We study a generalization of k-center clustering, first introduced by Kavand et. al., where instead of one set of centers, we have two types of centers, p red and q blue, and where each red center is at least α distant from each blue center. The goal is to minimize the covering radius. We provide an approximation algorithm for this problem, and a polynomial-time algorithm for the constrained problem, where all the centers must lie on a line ?.
BibTeX - Entry
@InProceedings{eskandari_et_al:LIPIcs.ISAAC.2021.41,
author = {Eskandari, Marzieh and Khare, Bhavika and Kumar, Nirman},
title = {{Separated Red Blue Center Clustering}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {41:1--41:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15474},
URN = {urn:nbn:de:0030-drops-154740},
doi = {10.4230/LIPIcs.ISAAC.2021.41},
annote = {Keywords: Algorithms, Facility Location, Clustering, Approximation Algorithms, Computational Geometry}
}
|
Keywords: |
|
Algorithms, Facility Location, Clustering, Approximation Algorithms, Computational Geometry |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
