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

Share/Save/Bookmark

Faigle, Ulrich and Kern, Walter (1998) An algebraic framework for the greedy algorithm with applications to the core and Weber set of cooperative games. [Report]

[img]
Preview
PDF
232Kb
Abstract:An algebraic model generalizing submodular polytopes is presented, where modular functions on partially ordered sets take over the role of vectors in ${\mathbb 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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65657
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141303