Skip to main navigation Skip to search Skip to main content

A characterization of non-negative greedy matrices

  • Ulrich Faigle
  • , Walter Kern

    Research output: Book/Report › Report › Professional

    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
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages12
    Publication statusPublished - 1993

    Publication series

    NameMemorandum
    PublisherUniversity of Twente, Department of Computer Science
    No.1172
    ISSN (Print)0924-3755

    Fingerprint

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

    • A characterization of non-negative greedy matrices

      Faigle, U., Hoffman, A. J. & Kern, W., 1996, In: SIAM journal on discrete mathematics. 9, 1, p. 1-6 6 p.

      Research output: Contribution to journal › Article › Academic › peer-review

      Open Access
      File
      5   Link opens in a new tab Citations (Scopus)
      256 Downloads (Pure)

    Cite this