We are given a hypergraph \(H=(V,E)\) and m groups \(E_1, E_2,\) \( \ldots , E_m \) of E, where each vertex in V has a cost, each (hyper-)edge in E has a profit and a penalty, and each group has a profit requirement. The prize-collecting hypergraph vertex cover with fairness constraints is to select a vertex set to minimize the total cost of the selected vertices and the total penalty of the uncovered edges subject to the fairness constraints, i.e., for each group \(E_i\) , the total profit of covered edges in \(E_i\) exceeds the profit requirement. In this paper, based on the LP-rounding technique and the guessing method, we design an f-approximation algorithm in \(n^{O(m/f)}\) time, where \(f=\max _{e:e\in E}|e|\) . Thus, when m is a constant, our algorithm is a polynomial-time f-approximation algorithm, which coincides with the lower bound of the hypergraph vertex cover problem if the unique game conjecture holds.

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

Approximation Algorithm for Prize-Collecting Hypergraph Vertex Cover with Fairness Constraints

  • Xiaofei Liu,
  • Weidong Li

摘要

We are given a hypergraph \(H=(V,E)\) and m groups \(E_1, E_2,\) \( \ldots , E_m \) of E, where each vertex in V has a cost, each (hyper-)edge in E has a profit and a penalty, and each group has a profit requirement. The prize-collecting hypergraph vertex cover with fairness constraints is to select a vertex set to minimize the total cost of the selected vertices and the total penalty of the uncovered edges subject to the fairness constraints, i.e., for each group \(E_i\) , the total profit of covered edges in \(E_i\) exceeds the profit requirement. In this paper, based on the LP-rounding technique and the guessing method, we design an f-approximation algorithm in \(n^{O(m/f)}\) time, where \(f=\max _{e:e\in E}|e|\) . Thus, when m is a constant, our algorithm is a polynomial-time f-approximation algorithm, which coincides with the lower bound of the hypergraph vertex cover problem if the unique game conjecture holds.