I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and papers, I've noticed that the Hungarian/Kuhn's algorithm tends to get mentioned a lot as a solution/approach. My sticking point is that it runs in $O(n^3)$ time and I've read in a few sources that there are better implementations.

My challenge is that these sources will often just mention these better approaches at the very end of a discussion and offer little insight into the implementation. So I guess my question is: are there indeed better than $O(n^3)$ runtimes? I think I remember coming across references that $O(nm\log n)$ and better exist, just having a hard time finding either reference implementations or more direction. Any help would be appreciated, especially examples as that's how I tend to grok things best after going through the theory.

up vote 0 down vote accepted

The Hungarian method can be implemented in time $O(mn + n^2 \log n)$. Details are found for example in Alexander Schrijver's book on Combinatorial Optimization, Chapter 17. For a more implementation-oriented guide to this version of the algorithm, have a look in Chapter 7 of Mehlhorn and Näher's book.

The running time is dominated by the time it takes to compute $n$ shortest paths via Dijkstra's algorithm. Each invocation of Dijkstra's algorithm costs $O(m + n \log n)$. (This assumes that Dijkstra's algorithm is implemented with Fibonacci heaps; the simpler implementation based on standard heaps would give $O(m \log n)$ for each invocation.)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.