Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\forall 1 \leq j \leq i, |S_j|>k$. The goal is to choose at most $k$ sets from each $S$ such that the number of elements covered by the chosen sets is maximized. Formally, the goal can be defined as:
$$argmax_{b_1 \subseteq S_1, |b_1|\leq k,...,b_i \subseteq S_i, |b_i| \leq k} \: |\cup_{a \in X} a|, where \;X= \cup_{j=1}^i b_j$$
One straightfoward approach is to adjust the standard greedy algorithm where we iteratively choose a set $a$ with the maximum marginal gain without breaking the choice constraint (i.e., k). However, I think that this strategy may not produce approximate solution.
Another potential solution to this problem I know is to adopt the continuous greedy method [1]. However, the computational cost is expensive.
Is there any efficient approximate algorithm for this problem with theoretical guarantees? The algorithm I am looking for does not need to have tight bounds but is expected to perform well in practice.
- Vondrák, Jan. "Optimal approximation for the submodular welfare problem in the value oracle model." Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008.
