Approximation algorithm for prize-collecting vertex cover with fairness constraints

Considering fairness has become increasingly important in recent research. This paper proposes the prize-collecting vertex cover problem with fairness constraints (FPCVC). In a prize-collecting vertex cover problem, those edges that are not covered incur penalties. By adding fairness concerns into the problem, the vertex set is divided into l groups, the goal is to find a vertex set to minimize the cost-plus-penalty value under the constraints that the profit of edges collected by each group exceeds a coverage requirement. In this paper, we propose a hybrid algorithm (combining deterministic rounding and randomized rounding) for the FPCVC problem which, with probability at least $$1-1/l^{\alpha }$$ 1 - 1 / l α , returns a feasible solution with an objective value at most $$\left( \frac{9(\alpha +1)}{2}\ln l+3\right) $$ 9 ( α + 1 ) 2 ln l + 3 times that of an optimal solution, where $$\alpha $$ α is a constant. We also show a lower bound of $$\Omega (\ln l)$$ Ω ( ln l ) for the approximability of FPCVC. Thus, our approximation ratio is asymptotically best possible. Experiments show that our algorithm performs fairly well empirically.