A characterization of nonnegative box-greedy matrices

Abstract

Given an ordering of the variables according to nonincreasing coefficients of the objective function cTx, the nonnegative matrix A is said to be greedy if, under arbitrary nonnegative constraint vectors 6 and h, the greedy algorithm maximizes cTx subject to Ax ≤ b, 0 ≤ x ≤ h. Extending a result of Hoffman, Kolen, and Sakarovitch for (0, 1)-matrices, we characterize greedy matrices in terms of forbidden submatrices, which yields polynomial recognition algorithms for various classes of greedy matrices. The general recognition problem for the existence of forbidden submatrices is shown to be NP-complete.