Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao zbMATH Openarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2012
Data sources: zbMATH Open
https://doi.org/10.4171/dms/6/...
Part of book or chapter of book . 2012 . Peer-reviewed
Data sources: Crossref
versions View all 2 versions
addClaim

Edmonds, matching and the birth of polyhedral combinatorics

Authors: Pulleyblank, William R.;

Edmonds, matching and the birth of polyhedral combinatorics

Abstract

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.

Keywords

History of mathematics in the 20th century, integer programming problem, Combinatorial optimization, matching algorithm, factors, Integer programming, weighted matching problem, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, nonbipartite matching, Analysis of algorithms, matchings, polyhedral combinatorics, integer programming

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    4
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
4
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!