On greedy algorithms, partially ordered sets, and submodular functions
Brenda L. Dietrich, A. J. Hoffman · IBM Journal of Research and Development · 2003
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.