Edmonds, matching and the birth of polyhedral combinatorics
William R. Pulleyblank · Documenta mathematica series · 2012
In the summer of 1961, Jack Edmonds, a twenty-seven year old mathematician, was attending a high powered workshop on combinatorics at the Rand Corporation in Santa Monica, California. His participation had been arranged by Alan Goldman, his manager at the National Bureau of Standards (now NIST), supported by Edmonds’ Princeton mentor, A.W. Tucker. It seemed to Edmonds that every senior academician doing combinatorics was there. This included such luminaries as George Dantzig, Alan Hoffman, Ray Fulkerson, Claude Berge and Bill Tutte. The only “kids” participating were Michel Balinski, Larry Brown, Chris Witzgall, and Edmonds, who shared an office during the workshop. Edmonds was scheduled to give a talk on his research ideas. At that time, he was working on some big questions. He had become intrigued by the possibility of defining a class of algorithms which could be proven to run more efficiently than exhaustive enumeration, and by showing that such algorithms existed. This was a novel idea. At this time, people were generally satisfied with algorithms whose running times could be proved to be finite, such as Dantzig’s Simplex Algorithm for linear programming. In 1958, Ralph Gomory [14], [15] had developed an analogue of the Simplex Algorithm that he showed solved integer programs in finite time, similar to the Simplex Algorithm. Many people in the Operations Research community viewed a problem as “solved” if it could be formulated as an integer programming problem. However, unlike the Simplex Algorithm, Gomory’s integer programming algorithm seemed to take so long on some problems that it was often unusable in practice. At this time, the combinatorics community was not very interested in algorithms. Generally, graphs considered were finite and so most problems had