On greedy and submodular matrices

Ulrich Faigle, Walter Kern, Britta Peis

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

85 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
EventFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011 - Rome, Italy
Duration: 18 Apr 201120 Apr 2011

Publication series

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

Conference

ConferenceFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
Period18/04/1120/04/11
Other18-20 April 2011

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