Key points are not available for this paper at this time.
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.
Duan et al. (Tue,) studied this question.