A CHARACTERIZATION OF NONNEGATIVE BOX-GREEDY MATRICES

Given an ordering of the variables according to nonincreasing coeffici ents of the objective function c(T)x, the nonnegative matrix A is said to be greedy if, under arbitrary nonnegative constraint vectors b and h, the greedy algorithm maximizes c(T)x subject to Ax less than or eq ual to b, 0 less than or equal to x less than or equal to h. Extending a result of Hoffman, Kolen, and Sakarovitch for (0, 1)-matrices, we c haracterize greedy matrices in terms of forbidden submatrices, which y ields polynomial recognition algorithms for various classes of greedy matrices, The general recognition problem for the existence of forbidd en submatrices is shown to be NP-complete