Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 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].

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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