Proving total dual integrality with cross-free families—A general framework

DOI10.1007/BF02591726MaRDI QIDQ3313630zbMATH OpenFDO

Authors Alexander Schrijver

Publication date 1984

Published in Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

total dual integralitytotal unimodularitypolymatroidal network flowscross-freekernel systemsubmodular, lattice polyhedra

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 3862931
• scientific article; zbMATH DE number 3885657
• On totally dual integral systems
• A polynomial-time test for total dual integrality in fixed dimension
• Publication:3033911

Cites work

• scientific article; zbMATH DE number 3862931 (Why is no real title available?)
• scientific article; zbMATH DE number 3906513 (Why is no real title available?)
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 3744939 (Why is no real title available?)
• scientific article; zbMATH DE number 3501242 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3634269 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A generalization of max flow—min cut
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• An Algorithm for Submodular Functions on Graphs
• Computing Maximal “Polymatroidal” Network Flows
• Lectures on matroids
• Maximal Flow Through a Network
• Min-max Relations for Directed Graphs
• Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
• Optimum matching forests I: Special weights
• Optimum matching forests II: General weights
• Optimum matching forests III: Facets of matching forest polyhedra
• Packing rooted directed cuts in a weighted directed graph
• Polyhedra related to a lattice
• Short proofs on the matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(11)

• An exact algorithm for the preemptive single machine scheduling of equal-length jobs
• A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
• Packing and covering of crossing families of cuts
• Characterizing and recognizing generalized polymatroids
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Generalized polymatroids and submodular flows
• Operations that preserve total dual integrality
• On box totally dual integral polyhedra
• An application of submodular flows
• scientific article; zbMATH DE number 3862931 (Why is no real title available?)
• An integer analogue of Carathéodory's theorem

This page was built for publication: Proving total dual integrality with cross-free families—A general framework

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