Abstract | ||
---|---|---|
Recent developments in the use of greedy algorithms in linear programming are reviewed and extended. We find a common generalization of some theorems of Queyranne—Spieksma— Tardella, Faigle—Kern, and Fujishige about greedy algorithms for linear programs in diverse contexts. Additionally, we extend a well-known theorem of Topkis about submodular functions on the product of chains to submodular functions on the product of lattices. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1147/rd.471.0025 | IBM Journal of Research and Development |
Keywords | Field | DocType |
greedy algorithm,linear program,partially ordered set | Maximum coverage problem,Mathematical optimization,Computer science,Submodular set function,Greedy algorithm,Real-time computing,Theoretical computer science,Greedy randomized adaptive search procedure,Partially ordered set | Journal |
Volume | Issue | ISSN |
47 | 1 | 0018-8646 |
Citations | PageRank | References |
11 | 0.86 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Brenda L. Dietrich | 1 | 11 | 0.86 |
Alan J. Hoffman | 2 | 11 | 1.20 |