An algebraic framework for the greedy algorithm with applications to the core and Weber set of cooperative games

Faigle, Ulrich and Kern, Walter (1999) An algebraic framework for the greedy algorithm with applications to the core and Weber set of cooperative games.
Technical Report , 23 p.

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.


Actions:
Download: [img] Postscript
Download (225kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik1999-362
Depositing User: Prof. Dr. Ulrich Faigle
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 14:21
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/362