On greedy and submodular matrices

Ulrich Faigle, Walter Kern, Britta Peis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

22 Downloads (Pure)

Abstract

We characterize non-negative greedy matrices, i.e., (0,1)-matrices A such that the problem max {c T x|Ax ≤ b, x ≥ 0} can be solved greedily. We identify so-called submodular matrices as a special subclass of greedy matrices. Finally, we extend the notion of greediness to { − 1,0,1}-matrices. We present numerous applications of these concepts.
Original languageEnglish
Title of host publicationTheory and Practice of Algorithms in (Computer) Systems
Subtitle of host publicationFirst International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings
EditorsAlberto Marchetti-Spaccamela, Michael Segal
Place of PublicationBerlin
PublisherSpringer
Pages116-126
Number of pages11
ISBN (Electronic)978-3-642-19754-3
ISBN (Print)978-3-642-19753-6
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6595
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Submodularity
  • Linear programming
  • Max flow

Fingerprint Dive into the research topics of 'On greedy and submodular matrices'. Together they form a unique fingerprint.

  • Cite this

    Faigle, U., Kern, W., & Peis, B. (2011). On greedy and submodular matrices. In A. Marchetti-Spaccamela, & M. Segal (Eds.), Theory and Practice of Algorithms in (Computer) Systems: First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings (pp. 116-126). (Lecture Notes in Computer Science; Vol. 6595). Berlin: Springer. https://doi.org/10.1007/978-3-642-19754-3_13