0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ This question seems closely related to your previous question on maximum coverage with set packing. May be worth combining the two. $\endgroup$ Commented Mar 9, 2014 at 23:06

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – R B
    Commented Mar 12, 2014 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.