Efficient Computation of Maximum Weighted Bipartite Matchings

Find the heaviest matching in a bipartite graph with respect to the edge weights. In the literature the assignment problem (Maximum Complete Weighted Bipartite Matching problem (MCWBM)) is often identified with the MWBM-problem. The solution for the assignment problem is the heaviest perfect matching, but there might be a heavier matching which is not perfect. If the possible solution is not restricted to the set of perfect matchings, the problem is harder. A solution for the MWBM-problem solves the assignment problem with a transformation w{ij} to w{ij} + C of the edge weights w{ij}.

The maximum weighted bipartite matching problem can be solved with a Primal- Dual-Algorithm in O(mn + n^2log(n)) worst case time on a graph with n nodes and m edges by augmenting successively along shortest paths. The class of augmenting path algorithms, which is strongly polynomial, has proven to be very efficient in practice for many optimization problems on matchings and provides therefore in many cases the algorithm of choice for an implementation.

Motwani has shown that for many matching algorithms, including one for the assignment problem, efficient worst case algorithms using the technique of augmenting along shortest paths perform well in the average case. For example the assignment problem takes time O(mlog(n)/log(Delta)). Delta is a measure for an expansion property of the input graph. The worst case bound for this algorithm, which is similar to Dinic's flow algorithm, is O(m square root of n).
Motwani's argument is based on the fact, that there exists always a very short augmenting path. But for the MWBM-problem, this argumentation does not work.

In the talk a new variant of the primal-dual-algorithm to calculate the maximum weighted bipartite matching is presented, whose expected running time is approximately O((m+n\log(n))\log n). The algorithm is
simpler and performs in practice much better than even the combination of the original primal-dual-algorithm and a heuristic preprocessing which is used in LEDA. The worst case bound of O(mn + n^2 \log(n)) is identical for both algorithms.