On the core of ordered submodular cost games |
| |
| Authors: | Ulrich Faigle Walter Kern |
| |
| Institution: | Mathematisches Institut, Zentrum für Angewandte Informatik, Universit?t zu K?ln, Weyertal 80, D-50931 K?ln, Germany, e-mail: faigle@zpr.uni-koeln.de, DE
Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands, NL
|
| |
| 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.
Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000 |
| |
| Keywords: | : core – N-person game – greedy algorithm – Monge property – order – polymatroid – poset – submodular |
| 本文献已被 SpringerLink 等数据库收录！ |
|
