<p>Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location.</p>

<p>J. Bar-Ilan, G. Kortsarz and D. Peleg, 
Generalized submodular cover problems and applications, 
Theoretical Computer Science, 250:179-200, 2001.</p>

CC BY-SA 3.0
2014-04-15T02:03:30.070Z
2014-04-15T02:03:30.070Z
Chandra Chekuri
<p>I am wondering if this is a studied variant of the Set Cover problem.</p>

<p>We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$.  We want to cover all elements in $X$ with sets $S'_i \subseteq S_i$ such that $|S'_i| \leq c_i$.  In other words we want to cover the elements with as few sets as possible but we are only allowed to use $c_i$ elements of each set. </p>

<p>The most similar variant I found is described in "Maximum Coverage Problem with Group Budget Constraints and Applications"</p>

<p>Thank you</p>

<np-hardness><set-cover>
Set cover with budget on sets
George
# Set cover with budget on sets

(Asked by: username_0 on 2014-04-15)

I am wondering if this is a studied variant of the Set Cover problem.

We are given a universe $X$, a collection of sets $S = \{S\_1, ..., S\_m\}$ and integers $c\_i$. We want to cover all elements in $X$ with sets $S'\_i \subseteq S\_i$ such that $|S'\_i| \leq c\_i$. In other words we want to cover the elements with as few sets as possible but we are only allowed to use $c\_i$ elements of each set.

The most similar variant I found is described in "Maximum Coverage Problem with Group Budget Constraints and Applications"

Thank you

**Tags:** np-hardness, set-cover

---

## 1 answers

### Answer by username_1 on 2014-04-15. Score: 5

Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location.

J. Bar-Ilan, G. Kortsarz and D. Peleg,
Generalized submodular cover problems and applications,
Theoretical Computer Science, 250:179-200, 2001.


---

