On 0, 1 matrices, odd vectors, and bisubmodular polyhedra

DOI10.1016/J.LAA.2006.08.033MaRDI QIDQ869913zbMATH OpenOpenAlexFDO

Authors Alexander V. Karzanov

Publication date 9 March 2007

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

Full work available at URL https://doi.org/10.1016/j.laa.2006.08.033

zbMATH Keywords

bisubmodular functioninteger solutionpolyhedronTDI-system

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Linear equations (linear algebraic aspects) (15A06) Matrices of integers (15B36)

Review text

This note describes a class of \(0,\pm 1\) matrices \(A\) that have the property that the equation \(Ay = c\), \(y \geq 0\) has an integer solution \(y\) for each odd vector \(c\), provided that there is already a rational solution. An application is to the integer solutions of a minimization problem.

Recommendations

• Publication:4729827
• Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
• On structures of bisubmodular polyhedra
• On the combinatorial structure of \(0/1\)-matrices representing nonobtuse simplices
• On nonsingularity of a polytope of matrices
• From Totally Unimodular to Balanced 0, ±1 Matrices: A Family of Integer Polytopes
• On the matroids in which all hyperplanes are binary
• Bisubmodular polyhedra, simplicial divisions, and discrete convexity
• On the minimal number of even submatrices of 0-1 matrices
• scientific article; zbMATH DE number 3869347

Cites work

• A greedy algorithm for solving a certain class of linear programmes
• A Min--Max Theorem for Bisubmodular Polyhedra
• Bisubmodular Function Minimization
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 8667 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Pseudomatroids

Cited in

(6)

• Dual systems of integer vectors and their applications to the theory of \((0,1)\)-matrices
• On the minimal number of even submatrices of 0-1 matrices
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• Birkhoff's polytope and unistochastic matrices, N=3 and N=4
• On the combinatorial structure of \(0/1\)-matrices representing nonobtuse simplices
• A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors

This page was built for publication: On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra

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