Using homogenous weights for approximating the partial cover problem

In this paper we consider the following natural generalization of two fundamental problems: the Set-Cover problem and the Min-Knapsack problem. We are given an hypergraph, each vertex has a nonnegative weight and each edge has a nonnegative length. For a given threshold (l) over cap, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of (l) over cap of the edges are covered. This problem is called the partial set cover problem. We present an O(\V\(2) + \H\) time, Delta(E)-approximation algorithm for this problem, where Delta(E) greater than or equal to 2 is an upper bound on the edge cardinality of the hypergraph, and \H\ is the size of the hypergraph (i.e. the sum of all its edges cardinalities). We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.