<p>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. <a href="http://epubs.siam.org/doi/abs/10.1137/S0097539700382820">http://epubs.siam.org/doi/abs/10.1137/S0097539700382820</a></p>

CC BY-SA 3.0
2016-05-07T15:57:10.650Z
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
CC BY-SA 3.0
2016-05-07T18:16:28.967Z
The analysis is in the paper.
Chandra Chekuri
CC BY-SA 3.0
2016-05-07T13:59:20.410Z
2016-05-07T13:59:20.410Z
Chandra Chekuri
<p>I have these two problems:</p>

<p><strong>Problem 1 (Dual bin packing problem)</strong></p>

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

<p><em>Question:</em> 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$.</p>

<p><strong>Problem 2 (Knapsack problem)</strong></p>

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

<p><em>Question:</em> 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$.</p>

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

<p>If we apply the following algorithm for dual bin packing problem : </p>

<pre><code>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
</code></pre>

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

<p>My attempt is: </p>

<p>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$.</p>

<p>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 &gt; ALG.
$$</p>

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

<approximation-algorithms><lower-bounds>
How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?
Jika
# How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

(Asked by: username_0 on 2016-05-06)

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

**Tags:** approximation-algorithms, lower-bounds

---

## 1 answers

### Answer by username_1 on 2016-05-07. Score: 6 | Accepted 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>

> **Comments:**
> **username_0**: 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$.  
> **username_1**: The analysis is in the paper.  

---

