title: Fast algorithms for finding optimal matchings on weighted bipartite graphs
body: <p>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 <a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=hungarianAlgorithm" rel="noreferrer">http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=hungarianAlgorithm</a>. 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.</p>