Fast algorithms for finding optimal matchings on weighted bipartite graphs

Question

I need to solve the assignment problem (given a complete weighted bipartite graph, choose a perfect matching with maximum total weight) efficiently and I've been using the O(n^3) version from here http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm. However, a paper I read mentioned a "more efficient method" in "A shortest augmenting path algorithm for dense and sparse linear assignment problems", which is sadly behind a paywall. Are there any faster algorithms that I should be aware of (either asymptotically, or just with smaller constants/more uniform memory access or whatever else)? I'm working with floating point weights rather than integer weights, which for the Hungarian method doesn't seem to matter, but might be an issue for faster integer implementations. Any relevant links would be much appreciated.

Answer 1

There are a few papers which have fast algorithms for weighted bipartite graphs.

A recent paper Ramshaw and Tarjan, 2012 "On Minimum-Cost Assignments in Unbalanced Bipartite Graphs" presents an algorithm called FlowAssign and Refine that solves for the min-cost, unbalanced, bipartite assignment problem and uses weight scaling to solve the perfect and imperfect assignment problems, but not incremental with a runtime complexity of O(m * sqrt(n) * log(n * C)) where m is the number of edges (a.k.a. arcs) in the graph, n is the maximum number of nodes in the two graphs to be matched, C is a constant greater than or equal to the maximum edge weight and is greater than or equal to 1.

The weight scaling is what allows the algorithm to achieve much better performance with respect to s where s is the number of matched nodes.

Other fast solutions can be found in the early 1990's. A paper from 1993 called "QuickMatch: A Very Fast Algorithm for the Assignment Problem" by Lee and Orlin proposes an algorithm whose runtime they estimate as effectively linear on the size of the graph in terms of arcs. http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf

The QuickMatch algorithm solves the assignment problem as a sequence of n shortest path problems. They use alternating shortest paths between origin nodes and destination nodes along with heuristics to decrease the number of calculations. The authors estimate the average runtime complexity by empirical results and comparisons to theoretically bounded algorithms. They find their algorithm to be linear w/ the number of graph edges (a.k.a. arcs), but the algorithm is not as performant as the "forward-reverse auction" algorithm of Bertsekas which also uses alternating shortest paths. The reference for the later was not printed in the paper, but might be in "Reverse auction algorithms for assignment problems", Castanon, 1992, MACS Seris in Discrete Mathematics and Computer Science

There is also the algorithm that the Berkeley segmentation benchmark code uses for bipartite matching during evaluation of segmentation results compared to human drawn boundaries. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ They use the Goldberg CSA package http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/code/CSA++/ which is reported to have runtime that is linear with graph size and solves for sparse min-cost assignment. The references are "An Efficient Cost Scaling Algorithm for the Assignment Problem", 1993 by Goldberg and Kennedy and Cherkassky and Goldberg, "On Implementing PushRelabel Method for the Maximum Flow Problem," Proc. Fourth Integer Programming and Combinatorial Optimization Conf., pp. 157- 171, May 1995.