In the set cover problem, the goal is to find a collection of subsets indexed by that minimizes such that
Consider the partial cover problem, in which one finds a collection of subset indexed by that minimizes such that
where is some constant.
- Give a polynomial-time algorithm to find a solution to the partial cover problem in which the value is no more than OPT, where is a constant that depends on , and OPT is the value of the optimal solution to the set cover problem.
- Give an -approximation algorithm for the partial cover problem, such that is non-decreasing in and .