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 max \ 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 min \ 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.
No takes yet. Share an insight, caveat, or question.
Hoffman et al. (1985) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: