Search Results

Documents authored by Khare, Bhavika


Document
Separated Red Blue Center Clustering

Authors: Marzieh Eskandari, Bhavika Khare, and Nirman Kumar

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


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 𝓁.

Cite as

Marzieh Eskandari, Bhavika Khare, and Nirman Kumar. Separated Red Blue Center Clustering. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ISAAC.2021.41},
  URN =		{urn:nbn:de:0030-drops-154740},
  doi =		{10.4230/LIPIcs.ISAAC.2021.41},
  annote =	{Keywords: Algorithms, Facility Location, Clustering, Approximation Algorithms, Computational Geometry}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail