A characterization of non-negative greedy matrices

Ulrich Faigle, Alan J. Hoffman, Walter Kern

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    86 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)1-6
    Number of pages6
    JournalSIAM journal on discrete mathematics
    Volume9
    Issue number1
    DOIs
    Publication statusPublished - 1996

    Keywords

    • Greedy algorithm
    • Linear program

    Fingerprint

    Dive into the research topics of 'A characterization of non-negative greedy matrices'. Together they form a unique fingerprint.

    Cite this