Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality

DOI10.1007/BF01590956zbMath0849.90095MaRDI QIDQ1919803

Michele Conforti, Cornuéjols, Gérard

Publication date: 18 September 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

coveringgeneralized set packingbalanced \(0, \pm1\)-matricesbicoloring theoremintegrality of polyhedratotal dual integrality results

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items

MIP reformulations of the probabilistic set covering problem, \((0,\pm 1)\) ideal matrices, Balanced matrices, Good and nice colorings of balanced hypergraphs, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Perfect \(0,\pm 1\) matrices, Transitive packing, Berge-acyclic multilinear 0-1 optimization problems, Perfect, ideal and balanced matrices, A characterization of oriented hypergraphic balance via signed weak walks, Perfect matchings in balanced hypergraphs, A polynomial recognition algorithm for balanced matrices, Balanced \(0,\pm 1\) matrices. I: Decomposition, Recognizing balanceable matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Minimax relations for the partial q-colorings of a graph
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• Normal hypergraphs and the perfect graph conjecture
• Balanced matrices and property (G)
• Algebraic Characterizations of Unimodular Matrices
• Balanced matrices