Key points are not available for this paper at this time.
Totally-balanced and greedy matrices are (0, 1) -matrices defined by excluding certain submatrices. For a n m \, (0, 1) -matrix A we show that the linear programming problem \ by yA c, 0 y d \ can be solved by a greedy algorithm for all c 0, d 0 and b₁ b₂ bₙ 0, if and only if A is a greedy matrix. Furthermore we show constructively that if b is an integer, then the corresponding primal problem \ cx + dz Ax + z b, x 0, z 0 \ has an integer optimal solution. A polynomial-time algorithm is presented to transform a totally-balanced matrix into a greedy matrix as well as to recognize a totallybalanced matrix. This transformation algorithm together with the result on greedy matrices enables us to solve a class of integer programming problems defined on totally-balanced matrices. Two examples arising in tree location theory are presented.
Hoffman et al. (Tue,) studied this question.