1
$\begingroup$

Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be assigned to one task, and one task can only have one worker. We want to find the maximum profit of all possible assignments.

Does anyone knows an algorithm or approach that can efficiently solve this problem and help provide a name or reference? Thank you.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

Your problem is known as the assignment problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is barely an answer. Convert to comment? $\endgroup$
    – Raphael ♦
    Oct 17, 2016 at 23:39
  • $\begingroup$ I don't think so. It's a complete answer. $\endgroup$
    – Yuval Filmus
    Oct 18, 2016 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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