TY - BOOK

T1 - A characterization of non-negative greedy matrices

AU - Faigle, Ulrich

AU - Kern, Walter

PY - 1993

Y1 - 1993

N2 - Given an ordering of the variables according to nonincreasing coefficients 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 \leq b,0 \leq x \leq 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.

AB - Given an ordering of the variables according to nonincreasing coefficients 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 \leq b,0 \leq x \leq 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.

M3 - Report

T3 - Memorandum

BT - A characterization of non-negative greedy matrices

PB - University of Twente, Faculty of Mathematical Sciences

CY - Enschede

ER -