# help to find An efficient algorithm

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.

• 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. – zdm Nov 7 '19 at 17:14
• 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. – Daniel Nov 7 '19 at 17:20
• we are speaking about approximately 10000 sets – Barak Mordehai Nov 7 '19 at 18:40

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.

• 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 – Barak Mordehai Nov 7 '19 at 18:29
• 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. – Steven Nov 7 '19 at 19:09