History of max-flow and min (bipartite) perfect matching

In class today Richard pointed out that a polynomial-time algorithm for min (bipartite) perfect matching was known prior even to the existence of linear programming.  This problem, also called the assignment problem, was implicitly shown to be solvable in polynomial time by the Hungarian Jenő Egerváry in 1931 (and perhaps arguably also by Dénes Kőnig in 1916).  This was not known in the West in the ’40s and early ’50s, when quite a few mathematicians (Merrill Flood, Julia Robinson, David Votaw, Alexander Orden) were thinking about the problem.  These people knew it could be solved using linear programming.

In 1955, Harold Kuhn published on the assignment problem.  He “discovered” Egerváry’s work (apparently it took him 2 weeks to translate the paper) and called the algorithm the “Hungarian Algorithm”.  He also showed how to solve the problem faster (quadratic time rather than quartic time, I think).

Also… in 1954, Ford and Fulkerson published on Max-Flow in some Rand tech report (the paper later appeared in a journal in 1956).  They knew that Max-Flow was solvable by LP, but they in particular showed it was also solvable in P (it was not known at the time that LP is solvable in P).  They also showed the Max-Flow = Min-Cut theorem (though it was only slightly later that people pointed out it was a special case of LP duality).  Finally, their algorithm also (implicitly) shows that if all the capacities are integers then so are the optimal solutions (Jamie asked about this).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: