Balanced matrices and the set covering polytope

الملخص EN

A (0>l)-matrix is said to be balanced if it does not contain any submatrix of odd order with exactly two ones in each row and each column.

A well-known necessary (but not sufficient) condition for a (0,l)-matrix A to be balanced is that the polytope associated with the linear programming relaxation of the set covering Problem associated with A has only integral vertices.

In this paper we characterize a class of (0,l)-matrices A for which the above condition is also sufficient for A to be balanced.

This provides at the same time a new class of facet defining inequalities for the general set covering polytope, where the coeffjcjents can arbjtrary elements in {0, 1, ..., p), the p being a specified positive integer.

Some applications to the Krcover problem and Kj-perfect graphs are also discussed.