Cornuejols book: Combinatorial Optimization

I had been reading this book on and off. Very nice presentation, just like the other books -- like Tarjan's book -- in the series by CBMS-NSF.

The interesting part is the material in chapter 6, which talks about {0,+1,-1} matrices. The picture on page 50 gives the relationship between the classes of {0,+1,-1} matrices. The four classes used in the book are PERFECT, IDEAL, BALANCED and TOTALLY UNIMODULAR. A balanced matrix is both perfect and ideal. The set of matrices which are TUM is a (strict) subset of balanced matrices.

I had talked in a couple of posts about TUM matrices. The posts are here. In this post we will see the generalizations of TUM matrices.

Let n(A) be a function which takes a {0,+1,-1} matrix and returns a column vector whose ith component is the number of -1's in the ith column of A.

Now, compare Ax and 1 - n(A) for some x in {0,1}^n. If

the former wins, we have a ideal matrix --> COVERING

the latter wins, we have a perfect matrix --> PACKING (how is it related to perfect graphs?)

if they are tied, we have a balanced matrix.
--
Refer to the matrix (on page 61) which is called the 0,1 extension of a {0,+1,-1} matrix.
--
A bipartite graph is said to be a perfect graph. What about directed bipartite graphs?
The book uses the term bigraph. According to wolfram, a bigraph is the same as a bipartite graph, which is possibly incorrect. A bigraph has signs on the edges.
--

Partially integral Polytopes: Our incidence matrix induces a polytope. We donot know if the vertices of this polytope are integral or not. The dimensions of this polytope is d. However, this polytope is not as important as the polytope of (n+d) dimensions. The interesting things is, this (n+d) dim polytope is partially integral, as the n vertices always induce integral vertices (IS THIS RIGHT???) the question remaining, what about the d vertices?