An Order-theoretic Framework for the Greedy Algorithm with Applications to the Core and Weber Set of Cooperative Games |
| |
Authors: | Faigle Ulrich Kern Walter |
| |
Institution: | (1) Mathematical Institute, Center for Applied Computer Science, University of Cologne, Weyertal 80, D-50931 Köln, Germany;(2) Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands |
| |
Abstract: | An algebraic model generalizing submodular polytopes is presented, where modular functions on partially ordered sets take over the role of vectors in R
n
. This model unifies various generalizations of combinatorial models in which the greedy algorithm and the Monge algorithm are successful and generalizations of the notions of core and Weber set in cooperative game theory.As a further application, we show that an earlier model of ours as well as the algorithmic model of Queyranne, Spieksma and Tardella for the Monge algorithm can be treated within the framework of usual matroid theory (on unordered ground-sets), which permits also the efficient algorithmic solution of the intersection problem within this model. |
| |
Keywords: | antimatroid coö perative game core greedy algorithm matroid Monge algorithm poset submodular Weber set |
本文献已被 SpringerLink 等数据库收录! |
|