Edmonds algorithm

The objective of the Edmonds algorithm is to find a perfect coupling (of maximum cardinal) in an assignment problem.

The coupling problem is as follows:

Construct a bipartite graph (the left-hand elements are only connected to right-hand elements by arcs, the right-hand elements do not have an outgoing arc) such that the elements on the left are the machines and the right-hand elements are the tasks to be performed. The arcs are of capacity 1 and cost according to the allocation table. If a flow passes by an edge (i, j), that is to say that the machine i performs the task j.
In order to complete the bipartite graph as a flow problem, each left-hand element is linked as a terminal vertex to a dummy source. Each element on the right is linked as the original vertex to a fictitious sink. All these arcs are of capacity 1 and cost 0. In order to solve the assignment problem, we apply a maximum cost-minimum flow algorithm to the constructed bipartite graph.

edmonds.png

 

Publicités