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

DOI10.1007/BF02591726zbMATH Open0531.90076MaRDI QIDQ3313630FDOQ3313630

Alexander Schrijver

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)