scientific article; zbMATH DE number 3862930

From MaRDI portal
Publication:3330973





[For the entire collection see Zbl 0533.00035.] Min-max relations in combinatorial optimization (typical example: Ford- Fulkerson's max-flow min-cut theorem) are of use in studying algorithms (they can serve as an optimality criterion, and they often follow as a by-product of an algorithm), and have theoretical interest (they often imply a polyhedral characterization). This paper gives a survey of min- max relations in combinatorial optimization. After introduction and preliminaries, it briefly reviews some methods: total unimodularity; total dual integrality; and blocking and anti-blocking polyhedra. Next the survey of results is centered around the following notions: bipartite graphs; network flows; matchings and generalizations; multicommodity flows; arborescences and directed cuts; perfect graphs; clutters and blockers; matroids and submodular functions. Some proofs are given, if they are illustrative for a typical method.




Cited in
(only showing first 100 items - show all)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3330973)