We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. We can represent this problem as the optimisation of the following quantity:

$I = argmax_{I} |\cup_{S_i \in I} S_i| - |I|$

What would be an efficient way to solve this optimisation problem?

We know from the inclusion-exclusion principle that the union of sets can be expressed as follows:

$|S_{i_1} \cup \dots \cup S_{i_k}| = \sum_{j=1}^{k} (-1)^{j+1} \sum_{1 \leq l_1, \dots, l_j \leq k} |S_{l_1} \cap \dots \cap S_{l_j}|$


Your problem is NP-hard. Given an instance $T_1,\ldots,T_n$ of Maximum Coverage, let $x_1,\ldots,x_n$ be new variables, and create an instance $S_1,\ldots,S_n$ of your problem, where $S_i = T_i \cup \{x_i\}$. We have $$ \left| \bigcup_{i \in I} S_i \right| -|I| = \left| \bigcup_{i \in I} T_i \right|. $$

On the positive side, consider the following greedy algorithm: $I_0 = \emptyset$, and for $k = 1,\ldots,n$, $I_k$ is obtained from $I_{k-1}$ by adding the set which maximizes the total number of elements covered by sets in $I_k$. It is known that for $k \in \{0,\ldots,n\}$, the set $I_k$ found by the greedy algorithm has the following property: for all sets $J_k$ of size $k$ we have $$ \left| \bigcup_{i \in I_k} S_i \right| \geq (1-1/e) \left| \bigcup_{i \in J_k} S_i \right|. $$ In particular, if the optimal solution to your problem has size $k$ and objective value $O$, then $$ \left| \bigcup_{i \in I_k} S_i \right| \geq (1-1/e)(O + k), $$ and so $$ \left| \bigcup_{i \in I_k} S_i \right| - k \geq (1-1/e) O - k/e. $$ The minimal optimal $k$ satisfies $O \geq k$ (each set adds at least one new element), and so $(1-1/e) O - k/e \geq (1-2/e) O$. This shows that the greedy algorithm (more explicitly, finding $k$ which maximizes $|I_k|-k$) gives a $1-2/e$ approximation to your problem (this can probably be improved).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.