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?)-


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?

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

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.

  • $\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
    Mar 12 '14 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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