# Hungarian Algorithm using BipartiteMatchingAndCover Function

I have a bipartite graph with two sets of vertices.

Needs["Combinatorica"]
g = CompleteGraph[3, 3];
edgeWeights = {{53, 96, 37}, {47, 87, 41}, {60, 92, 36}};
g1 = SetEdgeWeights[g, Flatten[edgeWeights]];


I want to find the optimal assignment that minimizes the total cost (sum of assigned edges). For this I use:

BipartiteMatchingAndCover[g1]


The answer I get is {{1, 5}, {2, 6}, {3, 4}}, which tells me that vertex 1 is assigned to vertex 5, 2 is assigned to 6 and 3 is assigned to 4. These assignments correspond to a total cost of 96+41+60 = 197. I would have expected the answer to be {{1,6},{2,4},{3,5}} which corresponds to a total cost of 37+47+92=176. It seems like the function is finding the assignments associated with the maximum cost instead of the minimum cost. I tried using 1/edgeWeights as edge weights, but got the same result.

Any ideas?

-

I think you're right about BipartiteMatchingAndCover returning a maximal matching. Instead of reciprocals, use negatives:

Needs["Combinatorica"]
g = CombinatoricaCompleteGraph[3, 3];
edgeWeights = {{53, 96, 37}, {47, 87, 41}, {60, 92, 36}};
g1 = CombinatoricaSetEdgeWeights[g, -Flatten[edgeWeights]];

CombinatoricaBipartiteMatchingAndCover[g1]
Extract[edgeWeights, First[%] /. x_ /; x > 3 :> x - 3]
Total[%]
(*
{{{1, 4}, {2, 5}, {3, 6}}, {-93, -87, -92, 40, 0, 56}}
{53, 87, 36}
176
*)


Note: There seem to be two optimal solutions.

-
Great. Thanks for your help MichelE2 ! – riveralebron Jul 14 '14 at 18:58
@riveralebron You're welcome. :) – Michael E2 Jul 14 '14 at 19:01
Just a pointer for future readers that the Combinatorica package's BipartiteMatchingAndCover has been superseded by the built-in FindIndependentEdgeSet` function as of Version 10. – DumpsterDoofus Oct 21 '14 at 15:50