On greedy and submodular matrices

Ulrich Faigle, Walter Kern, Britta Peis

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

2 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

Fingerprint

(0, 1)-matrices
Non-negative
Concepts

Keywords

  • Submodularity
  • Linear programming
  • Max flow

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
Faigle, Ulrich ; Kern, Walter ; Peis, Britta. / On greedy and submodular matrices. Theory and Practice of Algorithms in (Computer) Systems: First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings. editor / Alberto Marchetti-Spaccamela ; Michael Segal. Berlin : Springer, 2011. pp. 116-126 (Lecture Notes in Computer Science).
@inproceedings{a61cf8c18fa94100aeb021ea8abe0dba,
title = "On greedy and submodular matrices",
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.",
keywords = "Submodularity, Linear programming, Max flow",
author = "Ulrich Faigle and Walter Kern and Britta Peis",
note = "10.1007/978-3-642-19754-3_13",
year = "2011",
doi = "10.1007/978-3-642-19754-3_13",
language = "English",
isbn = "978-3-642-19753-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "116--126",
editor = "Alberto Marchetti-Spaccamela and Michael Segal",
booktitle = "Theory and Practice of Algorithms in (Computer) Systems",

}

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. Lecture Notes in Computer Science, vol. 6595, Springer, Berlin, pp. 116-126. https://doi.org/10.1007/978-3-642-19754-3_13

On greedy and submodular matrices. / Faigle, Ulrich; Kern, Walter; Peis, Britta.

Theory and Practice of Algorithms in (Computer) Systems: First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings. ed. / Alberto Marchetti-Spaccamela; Michael Segal. Berlin : Springer, 2011. p. 116-126 (Lecture Notes in Computer Science; Vol. 6595).

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

TY - GEN

T1 - On greedy and submodular matrices

AU - Faigle, Ulrich

AU - Kern, Walter

AU - Peis, Britta

N1 - 10.1007/978-3-642-19754-3_13

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Submodularity

KW - Linear programming

KW - Max flow

U2 - 10.1007/978-3-642-19754-3_13

DO - 10.1007/978-3-642-19754-3_13

M3 - Conference contribution

SN - 978-3-642-19753-6

T3 - Lecture Notes in Computer Science

SP - 116

EP - 126

BT - Theory and Practice of Algorithms in (Computer) Systems

A2 - Marchetti-Spaccamela, Alberto

A2 - Segal, Michael

PB - Springer

CY - Berlin

ER -

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