In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold Λ , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of Λ of the edges is covered. This problem is called the partial set cover problem. We present an O V 2 + H -time, E -approximation algorithm for this problem, where E β₯ 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). The special case where E = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O V 2 , is a dramatic improvement.
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.