2015 | OriginalPaper | Buchkapitel
Unit Covering in Color-Spanning Set Model
Autoren: Ehsan Emamjomeh-Zadeh, Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin
Verlag: Springer International Publishing
In this paper, we consider two new variants of the unit covering problem in color-spanning set model: Given a set of
n
points in
d
-dimensional plane colored with
m
colors, the
MinCSBC
problem is to select
m
points of different colors minimizing the minimum number of unit balls needed to cover them. Similarly, the
MaxCSBC
problem is to choose one point of each color to maximize the minimum number of needed unit balls. We show that MinCSBC is NP-hard and hard to approximate within any constant factor even in one dimension. For
d
= 1, however, we propose an ln (
m
)-approximation algorithm and present a constant-factor approximation algorithm for fixed
f
, where
f
is the maximum frequency of the colors. For the MaxCSBC problem, we first prove its NP-hardness. Then we present an approximation algorithm with a factor of 1/2 in one-dimensional case.
