<p>Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min_{i,j} b_i/A_{i,j}$ (which we can assume is at least $1$). If $A$ is a $0,1$ matrix and $b$ is an integer vector then this captures packing problems where one allows repetitions up to $\min_i b_i$. Packing problems become easier as width increases. For Set Packing one can get an approximation of the form $d^{1/W}$ where $W$ is the width and $d$ is the maximum set size and this is more or less tight from hardness of maximum independent set. In particular when $W = \Omega(\log d)$ one gets a constant factor approximation.</p>

CC BY-SA 3.0
2014-03-12T15:47:41.507Z
Thanks @Chandra, that makes sense.
The algorithm I have for the problem also work better as $r$ grows (in my definition), but I'm looking at it in a parametrized scenario, and my algorithm runs in exponential time in $k$ and finds the optimal packing.
R B
CC BY-SA 3.0
2014-03-10T14:23:28.187Z
2014-03-10T14:23:28.187Z
Chandra Chekuri
<p>In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the graph has to be vertex disjoint, in multidimensional matching every item has to appear once, etc.).</p>

<p>Are there any studied problems that ask for packing such that every item is packed at most $p$ times?</p>

<p>For example, is there any known reference for (perhaps under a different name?)-</p>

<p>$repetition-Set-Packing$:</p>

<p>given a universe $\mathcal{U}=\{e_1,..,e_n\}$, two numbers $k,r\in \mathbb{N}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that every item in $\mathcal{U}$ appears in at most $r$ sets in $S'$?</p>

<p>Are there any other works on packing with limitied repetitions?</p>

CC BY-SA 3.0
2014-03-09T23:06:37.733Z
This question seems closely related to your previous question on maximum coverage with set packing. May be worth combining the two.
Chandra Chekuri
<reference-request><packing><covering-problems>
Packing problems with repetitions
R B
# Packing problems with repetitions

(Asked by: username_0 on 2014-03-09)

In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the graph has to be vertex disjoint, in multidimensional matching every item has to appear once, etc.).

Are there any studied problems that ask for packing such that every item is packed at most $p$ times?

For example, is there any known reference for (perhaps under a different name?)-

$repetition-Set-Packing$:

given a universe $\mathcal{U}=\{e\_1,..,e\_n\}$, two numbers $k,r\in \mathbb{N}$ and a set of subsets $\mathcal{S}=\{s\_1,s\_2,...,s\_m\}\subseteq 2^\mathcal{U}$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$, $|\mathcal{S'}|=k$ such that every item in $\mathcal{U}$ appears in at most $r$ sets in $S'$?

Are there any other works on packing with limitied repetitions?

**Tags:** reference-request, packing, covering-problems
> **Comments:**
> **username_1**: This question seems closely related to your previous question on maximum coverage with set packing. May be worth combining the two.  

---

## 1 answers

### Answer by username_1 on 2014-03-10. Score: 4 | Accepted answer

Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min\_{i,j} b\_i/A\_{i,j}$ (which we can assume is at least $1$). If $A$ is a $0,1$ matrix and $b$ is an integer vector then this captures packing problems where one allows repetitions up to $\min\_i b\_i$. Packing problems become easier as width increases. For Set Packing one can get an approximation of the form $d^{1/W}$ where $W$ is the width and $d$ is the maximum set size and this is more or less tight from hardness of maximum independent set. In particular when $W = \Omega(\log d)$ one gets a constant factor approximation.

> **Comments:**
> **username_0**: Thanks @Chandra, that makes sense. The algorithm I have for the problem also work better as $r$ grows (in my definition), but I'm looking at it in a parametrized scenario, and my algorithm runs in exponential time in $k$ and finds the optimal packing.  

---

