A general ordertheoretic linear programming model for the study of matroid-type211u001egreedy algorithms is introduced. The primal restrictions are given by so-called 211u001eweakly increasing submodular functions on antichains. The LP-dual is solved by a 211u001eMonge-type greedy algorithm. The model offers a direct combinatorial explanation 211u001efor many integrality results in discrete optimization. In particular, the 211u001esubmodular intersection theorem of Edmonds and giles is seen for the case with a 211u001erooted forest as underlying structure. The core of associated polyhedra is 211u001eintroduced and applications to the existence of the core in cooperative game 211u001etheory are discussed.
展开▼