Cheap and Secure Web Hosting Provider : See Now

An algorithm to find the maximum profitable assignment

, , No Comments
Problem Detail: 

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.

Asked By : Tony
Answered By : Yuval Filmus

Your problem is known as the assignment problem.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback