A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors

DOI10.1016/0024-3795(84)90147-2zbMath0556.15011OpenAlexW1969749887WikidataQ56341653 ScholiaQ56341653MaRDI QIDQ761525

Satoru Fujishige

Publication date: 1984

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(84)90147-2

zbMATH Keywords

consistencysubmodular functionlinear inequalitiestotal dual integrality

Mathematics Subject Classification ID

Linear inequalities of matrices (15A39)

Related Items

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, A characterization of bisubmodular functions, Directed submodularity, ditroids and directed submodular flows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on Frank's generalized polymatroids
• On two minimax theorems in graph
• Proving total dual integrality with cross-free families—A general framework
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• Submodular systems and related topics
• A generalization of max flow—min cut