Size-Constrained Weighted Set Cover

In this paper, we introduce a natural generalization of Weighted Set Cover and Maximum Coverage, called Size-Constrained Weighted Set Cover. The input is a collection of n elements, a collection of weighted sets over the elements, a size constraint k, and a minimum coverage fraction ŝ; the output is a sub-collection of up to k sets whose union contains at least ŝn elements and whose sum of weights is minimal. We prove the hardness of approximation of this problem, and we present efficient approximation algorithms with provable quality guarantees that are the best possible. In many applications, the elements are data records, and the set collection to choose from is derived from combinations (patterns) of attribute values. We provide optimization techniques for this special case. Finally, we experimentally demonstrate the effectiveness and efficiency of our solutions.