Scholarlink

<p>Motivated by the scenario of assigning tasks of patching vulnerabilities to security administrators fairly to protect a network from malicious intrusions, we study a fair division problem of partitioning the set of hyperedges of a <i>k</i>-uniform hypergraph into <i>n</i> subsets for <i>n</i> agents in a balanced manner. The maximin share (MMS) fairness criterion is adopted, and the valuation of an agent is defined as the minimum vertex cover of the hyperedges she receives. The proposed fair division problem has an extra challenge since the computation of an agent’s valuation is strongly NP-hard. We show (in)approximability results of the problem and present two algorithms to compute approximate MMS fair allocations. We demonstrate that value <i>k</i>, the number of vertices in a hyperedge, has direct impacts on most of our (in)approximability results.</p>

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

Maximin share fair division of a k-uniform hypergraph

  • 期刊论文

  • 发表日期：

    2026年4月6日

查看全文
  • Bin Deng,
  • Hao Guo,
  • Weidong Li,
  • Jinwen Ou

摘要

Motivated by the scenario of assigning tasks of patching vulnerabilities to security administrators fairly to protect a network from malicious intrusions, we study a fair division problem of partitioning the set of hyperedges of a k-uniform hypergraph into n subsets for n agents in a balanced manner. The maximin share (MMS) fairness criterion is adopted, and the valuation of an agent is defined as the minimum vertex cover of the hyperedges she receives. The proposed fair division problem has an extra challenge since the computation of an agent’s valuation is strongly NP-hard. We show (in)approximability results of the problem and present two algorithms to compute approximate MMS fair allocations. We demonstrate that value k, the number of vertices in a hyperedge, has direct impacts on most of our (in)approximability results.