7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I believe that this falls under the class of problems called optimization problems $\endgroup$ – MatthewRock Jul 6 '16 at 15:31
  • 2
    $\begingroup$ @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? $\endgroup$ – Raphael Jul 6 '16 at 17:38
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael Jul 6 '16 at 17:40
  • $\begingroup$ @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. $\endgroup$ – MatthewRock Jul 7 '16 at 9:19
6
$\begingroup$

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.

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

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.

Thus, your problem is NP-hard.

Since it is also easy to express using integer programming, we can conclude it is NP-complete.

Regarding names, I don't know one. "Weighted Set Cover" is already taken for the variant where sets have costs, but I'd invent something around these lines. "Maximum-Weight Set Cover", maybe.

$\endgroup$
  • $\begingroup$ You don't need to ignore native speakers: each person of interest has a list of the languages they speak, and one of those is presumably their native language. Also, you seem to be optimizing in the opposite sense to what the question asks. You're answering the question, "What's the smallest number of translations that will allow everybody to understand?"; the question is asking "I have a fixed translation budget: what languages should I translate into to maximize the number of people who can understand?" $\endgroup$ – David Richerby Jul 6 '16 at 18:45
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 6 '16 at 18:47
  • $\begingroup$ @DavidRicherby I meant readers. It remains implicit in the question, but from the description I gathered that we'd have data on how many people can understand which language, precisely to optimize as you state. I apparently formulated in an easy to misunderstand way? $\endgroup$ – Raphael Jul 6 '16 at 22:30
  • $\begingroup$ @DavidRicherby It may be that we can not reach everyone within budget, which is of course the interesting case. That's where the problem diverges from plain Set Cover. $\endgroup$ – Raphael Jul 6 '16 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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