# Is there any algorithm for this (simple problem?)

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?

-
Google "maximum weighted bipartite matching" – Ben Derrett Sep 11 '11 at 14:04

I think you're looking for the Hungarian Algorithm.

-

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.

-
Surely if all the new edges have weight (==capacity?) 0, then the maximum flow is 0? – Ben Derrett Sep 11 '11 at 14:03

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.

-