1

Imagine you have:

  • 100 people
  • 100 projects

Each person ranks all 100 projects in the order in which they would like to work on them. What kind of algorithm can be used to maximize the happiness of the people (i.e. being assigned to a project they ranked higher translates to greater happiness).

Assume one project per person.

3

1 Answer 1

4

The algorithm for this kind of problems is very popular and is known as the Hungarian algorithm. The similar problem solved with this kind of problem:

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

Source: http://www.hungarianalgorithm.com/examplehungarianalgorithm.php

Please note that the default hungarian algorithm finds the minimum cost but you can alter the program to make it work as maximizing the cost.

If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

Source: http://en.wikipedia.org/wiki/Hungarian_algorithm

I've already implemented the Hungarian algorithm on my Github, so feel free to use it and modify it to make it work as maximizing the cost.

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.