Approximating the least core value and least core of cooperative games with supermodular costs

作者：Schulz Andreas S; Uhan Nelson A^*

来源：Discrete Optimization, 2013, 10(2): 163-180.

DOI：10.1016/j.disopt.2013.02.002

• Cooperative games
• Least core
• Approximation algorithms
• Scheduling
• Matroids

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-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. Published by Elsevier B.V.

• 出版日期2013-5