3
$\begingroup$

I'm trying to find An efficient algorithm for the following problem:

I have $n$ sets of numbers (different sets might have common numbers) and I need to find union combination of $k$ sets that Will yield the biggest set.

For example: if i have the sets $A1=\{1,3,4\}, A2=\{1,2,4\}, A3=\{5,7\}$ in that case $n=3$ and lets say that $k=2$. $|A1 \cup A3| =5$ or $|A2 \cup A3| =5$ will yield the biggest set In contrast to $|A1 \cup A2|$ = 4.

If this is np hard question (i don't know if it is) a good Approximation will be fine I think that brute force is $O({n \choose k})$ operations.

$\endgroup$
  • $\begingroup$ This is maximum coverage problem, an NP-hard problem. A greedy algorithm that chooses a set which contains the largest number of uncovered elements is $0.63$-approximation. $\endgroup$ – zdm Nov 7 '19 at 17:14
  • $\begingroup$ This looks very much like the Set Cover problem when you change your problem if you can cover all the numbers with k sets. For this problem there is no general constant factor approximation but one using the frequency as approximation factor ( in how many sets does a number appear?). I don't know how it generalizes to your problem where you want to maximize the covered numbers. $\endgroup$ – Daniel Nov 7 '19 at 17:20
  • $\begingroup$ we are speaking about approximately 10000 sets $\endgroup$ – Barak Mordehai Nov 7 '19 at 18:40
3
$\begingroup$

Your problem is known as the Maximum coverage problem. If $S$ is a solution (a set of at most $k$ sets), then an element is covered if it belongs to $\cup_{X \in S} X$. You want to find a solution that maximizes the number of covered elements. This problem is known to be $\textrm{NP}$-hard (see below for a possible reduction) and admits a greedy approximation algorithm that will cover at least a $\left( 1- \frac{1}{e} \right)$-fraction of the elements covered by an optimal solution.

In addition, there is an easy reduction from $3$-SAT to your problem.

Consider an instance of $3$-SAT with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. You can obtain an instance of your problem by creating two sets $T_i$ and $F_i$ for each variable $x_i$. The sets are defined as follows:

  • $T_i = \{ j \mid x_i \in C_j \} \cup A_i$ ;
  • $F_i = \{ j \mid \overline{x_i} \in C_j \} \cup A_i$,

where $A_1, \dots, A_n$ are arbitrary pairwise-disjoint sets, each containing $m+1$ integers between $m+1$ and $m+n(m+1)$.

Deciding whether you can select $n$ sets such that their union has cardinality at least $m+n(m+1)$ is now equivalent to deciding whether the $3$-SAT formula is satisfiable.

$\endgroup$
  • $\begingroup$ first of all thank you for the answer (1−1/e) -fraction is pretty low, is there average fraction i just want to know if i can count on it because its connected to my work $\endgroup$ – Barak Mordehai Nov 7 '19 at 18:29
  • $\begingroup$ What do you mean by "is there average fraction"? I am not an expert on this particular problem so I don't know more than what can be found online... The wikipedia page I linked claims that "lnapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless P = NP" and cites this paper by Uriel Feige. $\endgroup$ – Steven Nov 7 '19 at 19:09

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.