# Approximation Algorithm for the Partial Set Multi-Cover Problem

arXiv: https://arxiv.org/abs/1811.08185 · HTML: https://mlsanity.com/paper/1811.08185/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2018.

## Built on by (most cited first, 2 of 2)

- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)

## Abstract (arXiv)

Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets mathcal Ssubseteq 2E, a total covering ratio q which is a constant between 0 and 1, each set S∈mathcal S is associated with a cost cS, each element e∈ E is associated with a covering requirement re, the goal is to find a minimum cost sub-collection mathcal S'subseteqmathcal S to fully cover at least q|E| elements, where element e is fully covered if it belongs to at least re sets of mathcal S'. Denote by rmax=maxrecolon e∈ E the maximum covering requirement. We present an (O(fracrmaxlog2nvarepsilon),1-varepsilon)-bicriteria approximation algorithm, that is, the output of our algorithm has cost at most O(fracrmaxlog2 nvarepsilon) times of the optimal value while the number of fully covered elements is at least (1-varepsilon)q|E|.