October 6, 2011

## History of Khachiyan’s result

Khachiyan’s article outlining how to use the ellipsoid algorithm to solve linear programming in polynomial time appeared in Doklady in early 1979.  In late 1979, the great Gina Kolata wrote an extremely admirable article about it in Science.  The hysterical newspaper reports in the West were based on Kolata’s article.  This hilarious account of the situation by Lawler is a must-read.

September 20, 2011

## 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).