# Finding a fixed-size set whose members are contained by the largest number of other sets

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?

• I believe that this falls under the class of problems called optimization problems – MatthewRock Jul 6 '16 at 15:31
• @MatthewRock Yea. If you hand me an apple and ask me, "what kind of apple is that?" and I said, "It's some kind of fruit", what would your reaction be? – Raphael Jul 6 '16 at 17:38
• "Is there a name for the problem of covering a set with a fixed amount of other sets?" maybe? Well, I'd ask "Is there a name for Set Cover with fixed solution size?" but since you apparently did not know about Set Cover, that would not make sense. – Raphael Jul 6 '16 at 17:40
• @Raphael I believe that it's the other way around; I hand you a fruit and ask what it is. You tell me that it's "some kind of apple" or (more likely) that "it probably grows on tree". You did not answer my question, but maybe it could help me somehow - thus a comment, not an answer. Worst case: I just posted useless comment. A bit realistic case: someone learns something new. – MatthewRock Jul 7 '16 at 9:19

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.

• Nailed it. Welcome to the site! – David Richerby Jul 7 '16 at 9:56

If we ignore the number of native speakers of language for the moment, your problem is Set Cover -- you ask if it is possible to cover all languages with at most $k$ translators.

Adding weights -- the number of native speakers of each language -- adds a mode of optimization -- we may cover only some languages but want maximum total weight. This is certainly not easier; the reduction from Set Cover itself is trivial.

• Actually, this still gives a simpler proof of NP-hardness than mine. You can solve set cover by using binary search to find the minimum value of $k$ (the number of translations performed) such that the set of people reached is everyone. – David Richerby Jul 6 '16 at 18:47