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

U. Faigle, Walter Kern

Research output: Book/ReportReportProfessional

77 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages23
ISBN (Print)0169-2690
Publication statusPublished - 1998

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherUniversity of Twente, Department of Applied Mathematics
No.1468
ISSN (Print)0169-2690

Keywords

  • EWI-3288
  • MSC-90C27
  • METIS-141303
  • IR-65657
  • MSC-90D12

Cite this