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 itemsfor 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        breakHow 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$?
How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?
approximation algorithms;lower bounds
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