Some insight into characterizations of minimally nonideal matrices (Q2483016): Difference between revisions

A matrix is minimally nonideal if it is not ideal but all its proper minors are. The set covering problem is NP-complete for general 0-1 matrices. When the matrix is ideal then it can be solved as linear program for all objective functions. The authors present some properties of near-ideal matrices, and prove that a quasi minimally nonideal matrix whose core has at least two ones per column is a regular minimally nonideal matrix. The adjacency of the fractional extreme point of quasi minimally nonideal matrices obtaining a certain generalization property is studied. The authors also give a relationship between the stability and the covering numbers of regular minimally nonideal matrices, and prove when regular minimally nonideal matrices can be minors of quasi minimally nonideal matrices.