In this paper, we consider the colorful @math -center problem, which is a generalization of the well-known @math -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 @math , such that with @math balls of radius @math , 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.
A colorful version of vertex cover is studied in @cite_16 , and colorful versions of the Set Cover and Facility Location-type problems were considered in @cite_19 . In these problems, the cardinality of the cover (or its weight) shows up in the objective function, unlike in @math -center, where the number of centers balls @math is a hard restriction''. These problems therefore have a different flavor.
@cite_19 @cite_16
2890196309 2172398637
Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems. We consider a natural generalization of the Partial Vertex Cover problem. Here an instance consists of a graph G = (V,E), a cost function c: V → ℤ + , a partition P 1, …, P r of the edge set E, and a parameter k i for each partition P i . The goal is to find a minimum cost set of vertices which cover at least k i edges from the partition P i . We call this the Partition-VC problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of O(logr), where r is the number of sets in the partition of the edge set. We also extend our result to more general settings.