14
$\begingroup$

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important primal-dual method. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.

Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery. Thus, in answer of the following question, Jukka Suomela commented

Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.

In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.

My question is the following:

Is there a generalization of the Hungarian algorithm that works for general undirected graph without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?

I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!

Many thanks in advance and Merry Christmas!!!


Update: The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the weighted case) is Chapter 11 of Combinatorial Optimization by Korte and Vygen. Google book actually shows nearly all the parts I need to understand the algorithm.

$\endgroup$
  • 2
    $\begingroup$ How about Edmonds's matching algorithm? en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm $\endgroup$ – Arman Dec 24 '10 at 16:16
  • 1
    $\begingroup$ @Arman - That's what I was thinking, too. Thanks for the link, Wikipedia has a surprisingly detailed exposition of Edmond's blossom algorithm. $\endgroup$ – Abraham Flaxman Dec 24 '10 at 17:03
  • 2
    $\begingroup$ By the way, Edmonds's matching algorithm is also based on Primal-Dual method. $\endgroup$ – Arman Dec 24 '10 at 17:13
  • 1
    $\begingroup$ Thanks Arman. The wikipedia link also points to the book "Lovász, László; Plummer, Michael (1986). Matching Theory" for the weighted version of Edmonds's algorithm. I should really check that book out. Thank you very much for your comments! Maybe if any of you can explain in high level of how the algorithm generalizes the Hungarian algorithm, you can definitely make it an answer. $\endgroup$ – Dai Le Dec 24 '10 at 17:13
  • 1
    $\begingroup$ I think it's a pretty good answer as is :). Arman, you should add it as such $\endgroup$ – Suresh Venkat Dec 25 '10 at 5:09
16
$\begingroup$

Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.

There is also a correspondence between Blossom Algorithm and Primal Dual method. Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.

Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.

For details of the algorithm, see http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

For mathematical formulation and the corresponding primal-dual method, see http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf

$\endgroup$
9
$\begingroup$

Two years ago, when researching the (unweighted) blossom algorithm, I found two great sets of notes, one by Tarjan and one by Zwick. They made the unweighted case seem quite straightforward and I was able to implement it in Mathematica using recursion. It works quite well.

The notes that I found useful are

http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf and http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf

They distill it all down to very simple terms that allow one to think recursively and then, as noted, program recursively.

I think it should all work in the weighted case, which I trying to get implemented now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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