Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems

AbstractThis paper presents approximation algorithms for two extensions of the set cover problem: a graph-based extension known as the Max-Rep or Label-CoverMAXproblem, and a color-based extension known as the Red-Blue Set Cover problem. First, a randomized algorithm guaranteeing approximation ratio n with high probability is proposed for the Max-Rep (or Label-CoverMAX) problem, where n is the number of vertices in the graph. This algorithm is then generalized into a 4n-ratio algorithm for the nonuniform version of the problem. Secondly, it is shown that the Red-Blue Set Cover problem can be approximated with ratio 2nlogβ, where n is the number of sets and β is the number of blue elements. Both algorithms can be adapted to the weighted variants of the respective problems, yielding the same approximation ratios