2026-07-22T21:28:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11133 2024-03-06T10:47:31Z ddc:004 open_access

A Constant Approximation for Colorful k-Center Bandyapadhyay, Sayan Inamdar, Tanmay Pai, Shreyas Varadarajan, Kasturi Colorful k-center Euclidean Plane LP Rounding Outliers In this paper, we consider the colorful k-center problem, which is a generalization of the well-known k-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius rho, such that with k balls of radius rho, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a "pseudo-approximation" algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and Tanmay Inamdar and Shreyas Pai and Kasturi Varadarajan 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.12 urn:nbn:de:0030-drops-111336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.12 eng https://creativecommons.org/licenses/by/3.0/legalcode