Finding N elements that are included in as many sets as possible

Question

Say I have 20 sets, containing a variable amount of elements. How would I go about finding the 10 elements that cover the most number of sets?

Imagine I could search for three terms at once on Wikipedia. I know all the data in Wikipedia. Each page is a set of words. I want to search for the three terms that will return as many results as possible.

At first, it seems like searching for the most frequently occurring words is the best solution - this is probably fine for just three terms at once, but imagine ten thousand terms, on very small sets. The two most frequently occurring words tend to occur together in our sets (e.g, Happy Birthday) - we're trying to find something like the best orthogonal representation of all these sets, with N dimensions.

I haven't studied set theory yet, and although I am reading through Suppes' Axiomatic Set Theory nowadays, I'm sure I haven't formulated this problem in precise mathematical language, and I apologize for this. I am willing to clarify the problem more.

I'm looking for an algorithm, or a mathematical model that I could implement as an algorithm. Perhaps this question is better posited to StackOverflow!

Note that the result should be optimized but not necessarily perfect.

Answer 1

A possible mathematical formulation goes as follows: Let $X = \{x_1, \dots, x_N\}$ be the set of items under consideration and $A = \{A_1, \dots, A_M\}$ be the collection of sets. Define a bipartite graph with nodes $X \cup A$ and edge set $E = \{ (x_i, \, A_j) | x_i \in A_j\}$. If I understand correctly, you are interested in finding a subset $X_0 \subset X$ with given cardinality such that the set of $A_j \in A$ that are connected to $X_0$ has maximal cardinality.

A possible approach: Use a greedy algorithm.

Initialize by setting $A^{(0)} = A$. For $k = 1, 2, \dots$ define a sequence of $x^{(k)}$ as follows:

1. Given $A^{(k-1)}$, choose $x^{(k)}$ such that the set $\{A_j \in A^{(k-1)}| x^{(k)} \in A_j \}$ is maximal.

2. Set $A^{(k)} = A^{(k-1)} \setminus \{ A_j | x^{(k)} \in A_j \}$ and go to 1.

There may be algorithms from graph theory that do a better job.

Answer 2

The problem is known as the Maximum Coverage Problem. It is NP-hard. Thus we cannot solve it in polynomial time (≈efficiently) unless $P=NP$. A greedy algorithm gives a $1-1/e$ approximation and there is a matching hardness of approximation result [Hochbaum '97, Feige '98].

The problem is closely related to the Set Cover Problem: we are given a set of elements $X$ and a family of subsets $\cal S$ of $X$ (each $S\in \cal S$ is a subset of $X$); our goal is to choose the smallest possible number of sets in $\cal S$ that cover $X$. This problem is NP-hard [Karp' 72]. There is a $O(\log n)$ approximation algorithm for it and a matching hardness of approximation result [Lund, Yannakakis '94, Feige '98].