Balanced 0, ±1-matrices,bicoloring and total dual integrality |
| |
Authors: | Michele Conforti Gérard Cornuéjols |
| |
Affiliation: | (1) Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni 7, 35131 Padova, Italy;(2) Carnegie Mellon University, Schenley Park, 15213 Pittsburgh, PA, United States |
| |
Abstract: | A 0, ±1-matrixA is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, ±1-matrices.This work was supported in part by NSF grants DDM-8800281, ECS-8901495 and DDM-9001705. |
| |
Keywords: | Combinatorial optimization Integrality of polyhedra Generalized set packing Covering |
本文献已被 SpringerLink 等数据库收录! |
|