scientific article; zbMATH DE number 3862931
combinatorial optimizationcrossing familiesdirected graphdirected graphsmatching and covering theoremsmatroidsmax-flow min-cut theoremoptimum branchingsubmodular functionsupermodular functionssurveysystems of linear inequalitiestotal dual integralitytrees
Combinatorial aspects of matroids and geometric lattices (05B35) Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Deterministic network models in operations research (90B10) Linear programming (90C05) Integer programming (90C10) Mixed integer programming (90C11) Programming involving graphs or networks (90C35)
[For the entire collection see Zbl 0535.00030.] This paper surveys old and new results asserting the total dual integrality of certain systems of linear inequalities, involving directed graphs, crossing families, and sub- and supermodular functions. The basis is a proof technique set up by Edmonds, Giles, Hoffman, Johnson, Lovász and Robertson of first showing that the active constraints in the optimum of the linear program can be chosen to be nice (e.g. cross-free or laminar), and next that nice constraint sets are unimodular. This implies that the linear programs have integer optimum solutions. The results discussed are König's matching and covering theorems, Menger's theorem, Ford-Fulkerson's max-flow min-cut theorem, Dilworth's decomposition theorem for partially ordered sets, theorems on shortest paths, common SDR's and trees, Fulkerson's optimum branching theorem, the Lucchesi-Younger theorem, Nash-Williams' orientation theorem, Edmond's theorems on (poly)matroids and their intersection, extensions of these theorems to submodular flows by Edmonds, Giles, Frank, Tardos, Hoffman's theory of lattice polyhedra, Grishuhin's model, König's edge-colouring theorem, the Hoffman-Schwartz chain model, Edmonds' branching packing theorem, and results by the author on crossing families, strong connectors and supermodular colourings. A study is made of the interrelations between these results.
- Rooted \(k\)-connections in digraphs
- Generalized polymatroids and submodular flows
- Directed submodularity, ditroids and directed submodular flows
- Negative circuits for flows and submodular flows
- Coflow polyhedra
- Lattice matrices, intersection of ring families and dicuts
- Note on inverse problem with l_ objective function
- Discrete convex analysis
- Directed Steiner problems with connectivity constraints
- Optimum partitioning into intersections of ring families
- Switchdec polyhedra
- On the orientation of graphs and hypergraphs
- K-submodular functions and convexity of their Lovász extension
- Operations that preserve total dual integrality
- Lattice polyhedra and submodular flows
- The \(b\)-branching problem in digraphs
- Abstract flows over time: a first step towards solving dynamic packing problems
- A Survey on Covering Supermodular Functions
- Algorithms for submodular totally dual integral problems
- Proving total dual integrality with cross-free families - a general framework
- Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank
- Classes of linear programs with integral optimal solutions
- On box totally dual integral polyhedra
- scientific article; zbMATH DE number 123851 (Why is no real title available?)
- Characterizing and recognizing generalized polymatroids
- scientific article; zbMATH DE number 7378329 (Why is no real title available?)
- A notion of total dual integrality for convex, semidefinite, and extended formulations
- Duality for balanced submodular flows
- Total dual integrality of matching forest constraints
- An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint
- Approximately packing Dijoins via nowhere-zero flows
- Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
- A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
- Packing and covering of crossing families of cuts
- A note on Frank's generalized polymatroids
- Finding feasible vectors of Edmonds-Giles polyhedra
- A note on matchings and separability
- Restricted covering of digraphs with arborescences
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 Q3330974)