[Solved]: Finding a fixed-size set whose members are contained by the largest number of other sets

ignougroup
Problem Detail: I’ve been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to communicate with as many students as possible. Consider some finite population of people, each of whom speak any number of languages. For the purposes of the problem, we’ll ignore some of the things that make languages complex in real life (for example, that people speak several languages but at different levels, that people who understand one language might be able to understand closely-related languages, and so forth). So, for example:

  • P1 speaks {English, German}.
  • P2 speaks {Spanish, Italian, French}.
  • P3 speaks {Mandarin, English}.
  • P10000 speaks {Afrikaans, Swahili, English}, and so forth.

I am writing some document which I wish to have translated so as to be understood by as many people as possible. Unfortunately, my budget is limited, and I can only afford a translation into N different languages. For a given value of N, how do I calculate the optimimum set of N languages to reach the largest number of people out of the intended population? The problem sounds like it could be easily generalized as a set-theory/combinatorics problem, and so I’m certain somebody has done work on something like it before. I would like to take a look at the existing literature, but I don’t know how to find it. Is there a name for this type of problem? If not, could it be reduced to another known problem?

Asked By : tetrarchy

Answered By : Soeholm

I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover. From wikipedia, Maximum Coverage Problem:

As input you are given several sets and a number k. The sets may have some elements in common. You must select at most k of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.

So, in your case, there is a set for each language with cardinality equal to the number of students speaking that language. The input is the number N of maximum number of translations.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60361