Abstract
A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed.
Original language | Undefined |
---|---|
Pages (from-to) | 483-499 |
Number of pages | 16 |
Journal | Mathematical programming |
Volume | 87 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2000 |
Keywords
- core –N-person game – greedy algorithm – Monge property – order – polymatroid – poset – submodular
- METIS-140636
- IR-79986