Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Duan et al. (2012) studied this question.