Optimization Online


Approximating the Least Core Value and Least Core of Cooperative Games with Supermodular Costs

A. S. Schulz (schulz***at***mit.edu)
N. A. Uhan (uhan***at***usna.edu)

Abstract: We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.


Category 1: Other Topics (Game Theory )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Discrete Optimization, available online, March 2013. DOI: 10.1016/j.disopt.2013.02.002


Entry Submitted: 06/23/2010
Entry Accepted: 07/02/2010
Entry Last Modified: 03/25/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society