A Constant Approximation for Colorful k-Center

Sayan Bandyapadhyay; Tanmay Inamdar; Shreyas Pai; Kasturi Varadarajan

doi:10.4230/lipics.esa.2019.12

Back

A Constant Approximation for Colorful k-Center

Conference proceeding

Open access

A Constant Approximation for Colorful k-Center

Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai and Kasturi Varadarajan

Leibniz International Proceedings in Informatics, LIPIcs, Vol.144

07/20/2019

DOI: 10.4230/lipics.esa.2019.12

Files and links (1)

url

https://doi.org/10.4230/lipics.esa.2019.12View

Published (Version of record) Open Access

Abstract

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.

Algorithms

Computational Geometry

Computer Science

Data Structures

Details

Title: Subtitle: A Constant Approximation for Colorful k-Center
Creators: Sayan Bandyapadhyay
Tanmay Inamdar
Shreyas Pai
Kasturi Varadarajan
Resource Type: Conference proceeding
Publication Details: Leibniz International Proceedings in Informatics, LIPIcs, Vol.144
DOI: 10.4230/lipics.esa.2019.12
ISSN: 1868-8969
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Language: English
Date published: 07/20/2019
Academic Unit: Computer Science
Record Identifier: 9984259425602771

Metrics

28 Record Views