ISSN:
1436-4646
Keywords:
Combinatorial optimization
;
Integrality of polyhedra
;
Generalized set packing
;
Covering
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01590956
Permalink