Some insight into characterizations of minimally nonideal matrices

DOI10.1007/S00186-007-0176-7MaRDI QIDQ2483016zbMATH OpenOpenAlexFDO

Authors Gabriela R. Argiroffo, Silvia M. Bianchi, G. Nasini

Publication date 5 May 2008

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-007-0176-7

zbMATH Keywords

set covering polyhedra

Mathematics Subject Classification ID

Boolean programming (90C09) Combinatorial optimization (90C27)

Review text

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.

Recommendations

• Lehman's forbidden minor characterization of ideal 0-1 matrices
• Ideal 0, 1 matrices
• Near-perfect matrices
• (0, 1) ideal matrices
• On the set covering polyhedron of circulant matrices

Cites work

• A catalog of minimally nonideal matrices
• Bottleneck extrema
• Combinatorial designs and related systems
• Combinatorial optimization. Packing and covering
• scientific article; zbMATH DE number 5158506 (Why is no real title available?)
• scientific article; zbMATH DE number 16723 (Why is no real title available?)
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• On a certain class of nonideal clutters
• On the width—length inequality
• The matroids with the max-flow min-cut property

Cited in

(6)

• A catalog of minimally nonideal matrices
• The nonidealness index of circulant matrices
• \((0, \pm 1)\) ideal matrices
• scientific article; zbMATH DE number 2198001 (Why is no real title available?)
• A new infinite family of minimally nonideal matrices
• Vertex adjacencies in the set covering polyhedron

This page was built for publication: Some insight into characterizations of minimally nonideal matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483016)