Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a table like this:

    a    b    c    d    e    f
A   2.3  4.2  1.1  2.0  7.7  0.8
B   2.2  1.0  4.4  4.3  4.5  4.4
C   1.2  1.2  3.2  3.4  4.3  4.3
D   1.8  8.1  2.3  2.6  2.5  2.0

From A to D are places, from a to f are people. Each number means the "distance" of the corresponding people from place. For example, from A to a is 2.3 units long.

Now I want 4 of the people to choose a place to go. No one goes to more than one place and no place should have more than one people, (but 2 of the people are not going,) so that the total distance is the minimum possible.

For example, If A-a, B-b, C-c and D-d, you get 2.3 + 1.0 + 3.2 + 2.6 = 8.1. But if you make it A-c, B-b, C-a and D-f, you'll get 1.1 + 1.0 + 1.2 + 2.0 = 5.3 which is better.

I want a algorithm than can be programmed to find the best plan. Is there any algorithm for this?

share|improve this question
1  
Google "maximum weighted bipartite matching" –  Ben Derrett Sep 11 '11 at 14:04
add comment

3 Answers

I think you're looking for the Hungarian Algorithm.

share|improve this answer
add comment

You can make this into a bipartite graph, where people are on the left, and places are on the right. Add all edges between people and places, with weight = N - distance. (Where N is greater than any distance). Add a vertex to the left of the people, attached to all people vertices, and an edge to the right of places, attached to all places vertices. These new edges have weight 0, (or 1, does not matter).

What you now seek is "max flow" of this graph, where water flows from left to right, see http://en.wikipedia.org/wiki/Maximum_flow_problem

You can probably modify http://en.wikipedia.org/wiki/Maximum_cardinality_matching to your problem.

share|improve this answer
    
Surely if all the new edges have weight (==capacity?) 0, then the maximum flow is 0? –  Ben Derrett Sep 11 '11 at 14:03
add comment

If it is that small, just brute force it. If it is medium size you can brute force with a branch and bound where you stop the DFS and backtrack when one of your properties are violated.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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