An order-theoretic framework for the greedy algorithm with applications to the core and Weber Set of cooperative games

U. Faigle, Walter Kern

Research output: Contribution to journalArticleAcademic

9 Citations (Scopus)

Abstract

An algebraic model generalizing submodular polytopes is presented, where modular functions on partially ordered sets take over the role of vectors in Rn. 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.
Original languageUndefined
Pages (from-to)353-375
JournalOrder
Volume17
Issue number4
DOIs
Publication statusPublished - 2000

Keywords

  • IR-85187

Cite this