Edmonds, matching and the birth of polyhedral combinatorics (Q1946018)

It is always good to read the history and learn from it. An extra volume of \textit{Documenta Mathematica}, \textit{Optimization Stories}, provides wonderful reviews on historical people, events and important results in the field of optimization. The paper is one of those which appear in this volume. The story is centered around the matching algorithm in general (relative to bipartite) graphs of Edmonds, which was developed in the 1960's. It is comprehensive retrospect to the important results in matching theory including Berge's theorem, Kőnig's theorem, Hall's theorem, Egerváry's theorem, Tutte's theorem and the Tutte-Berge formula, which were the motivation and the basis of the algorithm of Edmonds. The author describes some scenes when Edmonds developed his idea of odd cycle contraction on a workshop at Rand, and briefly explains the main ideas of the matching algorithm. In one respect, the importance of the algorithm lies in the fact that it was an early algorithm that runs in polynomial time, which Edmonds highlighted as a mathematically precise measure that capture the idea of ``better than finite''. The concept of good algorithm and good characterization later became essential ideas embodied in the classes \(\mathcal{P}\) and \(\mathcal{NP}\). The paper also talks about the generalization of the algorithm to a weighted version, and the consequent generalization of the idea to many variant of the matching problems, such as the \(b\)-matching problems, capacitated \(b\)-matching problem (with parity constraints) and bidirected graphs. In response to the title, the last section describe the influence of Edmonds' work on combinatorial polyhedra. The weighted matching problem could be naturally formulated as an integer programming problem. Edmonds had shown that, this integer programming could be transformed to a linear programming, by adding to it a set of linear inequalities called cuts. And the weighted matching problem was the first known combinatorial problem in which the integrality constraint could be replaced by cuts. Therefore, this work became a motivation for the active research area of facet determination, which looks for linear systems to transform integer programs to linear programs.