Publications of Paolo Nobili

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1994, with author Nobili P., in the category IASI Research Reports (or show them all):


IASI Research Report n. 392  


Nobili P., Sassano A.

(0,? 1) Ideal matrices

ABSTRACT
A (0, 1) matrix A is said to be ideal if all the vertices of the polytope Q (A) = {x : Ax ≥1,0 ≤ x ≤ 1} are integral. The issue of finding a satisfactory characterization of those matrices which are minimally non-ideal is a well known open problem. An outstanding result toward the solution of this problem, due to Alfred Lehman, is the description of crucial properties of minimally non-ideal matrices. In this paper we consider the extension of the notion of ideality to (0, ? 1) matrices. By means of a standard transformation, we associate with any (0, ? 1) matrix A^+ a suitable (0, 1) matrix D(A). Then we introduce the concept of disjoint completion A of a (0, ? 1) matrix A and we show that A is ideal if and only if D(A^+) is ideal. Moreover, we introduce a suitable concept of a minimally non-ideal (0, ? 1) matrix and we prove a Lehman-type characterization of minimally non-ideal (0, ? 1) matrices that coincide with their disjoint completion.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -