# How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

I have these two problems:

Problem 1 (Dual bin packing problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$.

Question: Find the maximum number of items that can be packed into the $k$ bins such that each bin $j$ has a set of items of weights no more than $W$.

Problem 2 (Knapsack problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. One bin of capacity $W$.

Question: Find the maximum number of items that can be packed into the bin such that it has a set of items of weights no more than $W$.

Now given a set of items $\{w_1, \ldots, w_n\}$ and a set of $k$ bins.

If we apply the following algorithm for dual bin packing problem :

S = set of items
for each bin j do
Solve the knapsack problem on bin j and save the result on OPT[j]
\\ OPT[j] is the set of items packed into bin j.
Update S by removing the items in OPT[j]
\\ S = S - OPT[j]
if S is empty do
break


How can the output of this algorithm compared to the optimal solution of the dual bin packing problem?

My attempt is:

Let us denote by $OPT_b$ the optimal value of problem 1. That is, $OPT_b$ is the maximum number of items that are packed into the $k$ bins. Moreover, let us denote by $OPT_j$ the optimal number of items that are packed into bin $j$ by solving problem 2 on bin $j$. That is $OPT_j$ is the optimal value of problem 2 when applied to bin $j$. In other words, the output of the algorithm, denoted $ALG$, is equal to $\sum_{j=1}^{k}OPT_j$.

We have $$OPT_b \geq ALG,$$ because, otherwise, $ALG$ will be greater than $OPT_b$ which contradicts the optimality of $OPT_b$. But can we prove the other inequality? More probably, it is not possible to obtain the other inequality. Hence, we can argue that it could be true, sometimes, that $$OPT_b > ALG.$$

So can we give a bound on $ALG$ like $$ALG\geq \rho OPT_b,$$ for some $\rho$?

## 1 Answer

The "dual bin packing problem" is more commonly referred to as the Multiple Knapsack problem. One can show that $ALG \ge (1-1/e) OPT_b$ assuming an optimal algorithm for the Knapsack problem is used in each bin. If the bins are of different sizes then one can show that $ALG \ge OPT_b/2$ irrespective of the order in which the bins are processed. See Section 4 in the paper below for these results. http://epubs.siam.org/doi/abs/10.1137/S0097539700382820

• Thanks. Interesting paper. Can you provide some ideas how would I drive the $(1-1/e)$ bound. Because I was trying to lower bound $ALG$ and I get the following result: Assume that $OPT^i$ is the optimal knapsack algorithm used for bin $i$, $i=1,2,\ldots,k$. Now, let us look at the optimal solution for the multiple knapsack problem (dual bin packing problem) $OPT_b$ at each bin $i$, denoted $OPT_b(i)$ ($OPT_b=\sum_{i=1}^{k}OPT_b(i)$). We have $OPT_b(i)\leq OPT^1$ for all $i$. Thus, $OPT_b\leq k OPT^1$. Finally, $OPT_b/k\leq \sum_{i=1}^{k}OPT^i=ALG$. – Jika May 7 '16 at 15:57
• The analysis is in the paper. – Chandra Chekuri May 7 '16 at 18:16