3
$\begingroup$

First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case.

The problem:

We are given a set of $m$ workers $A = \{ a_1, a_2,...a_m \}$ and a set of $n$ tasks $T = \{ t_1, t_2,...,t_n \}$. Each worker either can or cannot perform any given task and there is no cost associated with a task. The set of tasks that can be performed by a single worker $a_i$ is $T_{a_i} \subset T$. The set of tasks that can be performed by a subset of $s$ workers is given by the union of the tasks each individual worker can perform $\bigcup_{i=1}^{s} T_{a_i}$ (not necessarily the first $s$ workers).

The problem is to select $s$ workers such that the number of task that can be performed is maximized, i.e. maximize the number of elements in $\bigcup_{i=1}^{s} T_{a_i}$.

I couldn't find which category of problems this belong to, let alone any solutions. Any help in this matter would be greatly appreciated!

$\endgroup$
1
$\begingroup$

Your problem is known as maximum coverage.

$\endgroup$
  • $\begingroup$ Thank you for the quick answer! $\endgroup$ – grescha Sep 11 at 5:58

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.