• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Approximating the least core value and least core of cooperative games with supermodular costs
【24h】

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

机译：用超模块化成本估算合作游戏的最低核心价值和最低核心

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：我们研究了超模块化成本合作博弈的最小核心价值和最小核心的近似。我们提供了一个基于oracle的近似框架，可以近似确定最大违反约束条件。该框架产生了一个3-近似算法，用于计算超模块化成本合作博弈的最小核心价值，以及一个多项式时间算法，用于计算这些博弈的2-近似最小核中的成本分配。这种近似框架自然地扩展到了次模块化的利润合作博弈。对于调度游戏（一类特殊的超模块化成本合作游戏），我们给出了用于计算最小核心价值的完全多项式时间近似方案。对于拟获类特殊利益的亚模块获利合作博弈，我们给出了精确的多项式时间算法，用于计算最小核心价值和最小核心成本分配。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号