@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 ; First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011 ; Conference date: 18-04-2011 Through 20-04-2011",

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",

address = "Netherlands",

}