Advertisement
Published in:
2015 | OriginalPaper | Chapter
Unit Covering in Color-Spanning Set Model
Authors : Ehsan Emamjomeh-Zadeh, Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.