Fast algorithms for finding optimal matches on weighted bipartite graphs

Question

I need to solve the assignment problem (given the full weighted bipartite graph, choose the perfect match with the maximum total weight), and I used the O (n ^ 3) version here http://community.topcoder.com/tc?module=Static&d1=tutorials&d2= hungarianAlgorithm . However, the document I read mentions the “more efficient method” in the “shortest extended path algorithm for dense and sparse linear assignment problems”, which, unfortunately, is behind the fee. Are there any faster algorithms that I should be aware of (either asymptotically, or simply with less constants / more uniform access to memory, or something else)? I work with floating point weights, not integer weights, which for the Hungarian method does not seem to matter, but it can be a problem for faster integer implementations. Any relevant links would be highly appreciated.

Answer 1

There are several documents that have fast algorithms for weighted bipartite graphs.

A recent article by Ramshaw and Taryan “On assignment of minimum costs in unbalanced bipartite graphs” presents the FlowAssign and Refine algorithm, which solves the problem of minimum cost, imbalance, bipartite assignment and uses weight scaling to solve ideal and imperfect assignment problems, but not incremental with complexity run O (m * sqrt (n) * log (n * C)) where m is the number of edges (aka arcs) in the graph, n is the maximum number of nodes in the two graphs that must be mapped, C is a constant, greater or equal to the maximum weight of the edge and greater than or equal to 1.

Weight scaling is what allows the algorithm to achieve much higher performance with respect to s where s is the number of matched nodes.

Other quick fixes can be found in the early 1990s. The 1993 document "QuickMatch: A Very Fast Algorithm for the Assignment Problem" by Lee and Orlin proposes an algorithm whose execution time they estimate as efficiently as the graph size in arcs. http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf

The QuickMatch algorithm solves the assignment problem as a sequence of n shortest paths. They use alternating shortest paths between origin and destination nodes along with heuristics to reduce the number of calculations. The authors evaluate the average complexity of performing empirical results and comparisons with theoretically limited algorithms. They find that their algorithm is linear w / the number of edges of the graph (arcs aka), but the algorithm is not as productive as the “direct call auction”, Bercekas's algorithm, which also uses alternating shortest paths. A link for a later one was not printed in the newspaper, but could have been in "Reverse Auction Algorithms for Assignment Problems", Castanon, 1992, MACS Seris in Discrete Mathematics and Computer Science

There is also an algorithm that Berkeley segmentation reference code is used for two-way comparison when evaluating segmentation results compared to human 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 reportedly has a runtime that is linear with the size of the graph and decides for a sparse assignment of minimum cost. References "An Effective Cost Scaling Algorithm for an Assignment Problem," 1993 by Goldberg and Kennedy and Cherkassky and Goldberg, "On Implementing the PushRelabel Method for a Max Flow Task," Proc. Fourth Integer Programming and Combinatorial Optimization Conf., Pp. 157-171, May 1995.

Answer 2

it can be equally transformed into a minimum cost problem, min cost, you can check it.

AFAIK, Hungarian is the fastest.