Scholarlink

<p>This paper considers approximate cores of submodular cost set cover games. A submodular cost set cover game involves a finite set of players, an index set, and a submodular function defined on the index set. Each element in the index set corresponds to a subset of the player set and the union of all these subsets equals the entire player set. Given a subset of players, call a subset of the index set a cover of it if the union of the corresponding sets contains all the players in the subset. For any subset of players, its cost is the minimum submodular function value over all possible set covers of the subset. In this paper, we study the non-emptiness property of the approximate cores of submodular cost set cover games from the perspective of the integrality gap of the mathematical program for submodular cost set cover optimization problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximate Cores of Submodular Cost Set Cover Games

  • 期刊论文

  • 发表日期：

    2025年8月13日

查看全文
  • Qingqin Nong,
  • Jingyu Yao,
  • Xin Qin,
  • Suning Gong,
  • Qizhi Fang

摘要

This paper considers approximate cores of submodular cost set cover games. A submodular cost set cover game involves a finite set of players, an index set, and a submodular function defined on the index set. Each element in the index set corresponds to a subset of the player set and the union of all these subsets equals the entire player set. Given a subset of players, call a subset of the index set a cover of it if the union of the corresponding sets contains all the players in the subset. For any subset of players, its cost is the minimum submodular function value over all possible set covers of the subset. In this paper, we study the non-emptiness property of the approximate cores of submodular cost set cover games from the perspective of the integrality gap of the mathematical program for submodular cost set cover optimization problems.