A scaling algorithm for maximum weight matching in bipartite graphs
Ran Duan, Hsin-Hao Su · 2012
Given a weighted bipartite graph, the maximum weight matching (MWM) problem is to find a set of vertex-disjoint edges with maximum weight. We present a new scaling algorithm that runs in O(m √ n log N) time, when the weights are integers within the range of [0, N]. The result improves the previous bounds of O(Nm √ n) by Gabow and O(m √ n log (nN)) by Gabow and Tarjan over 20 years ago. Our improvement draws ideas from a not widely known result, the primal method by Balinski and Gomory.