Edmonds, matching and the birth of polyhedral combinatorics
type: Item
instance of: scholarly article
title: Edmonds, matching and the birth of polyhedral combinatorics
zbMATH Open document ID: 1276.05096
published in: Documenta Mathematica
publication date: 2013-04-17T00:00:00Z
full work available at URL: 34 pulleyblank-william.html
review text: 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 proble…
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 01A60
zbMATH DE Number: 6155089
zbMATH Keywords: matchings
zbMATH Keywords: matching algorithm
zbMATH Keywords: factors
zbMATH Keywords: polyhedral combinatorics
zbMATH Keywords: nonbipartite matching
zbMATH Keywords: integer programming
zbMATH Keywords: weighted matching problem
zbMATH Keywords: integer programming problem
author: William R. Pulleyblank
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6155089