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).
Leave a Reply