3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Jika
    May 7, 2016 at 15:57
  • 1
    $\begingroup$ The analysis is in the paper. $\endgroup$
    – Chandra Chekuri
    May 7, 2016 at 18:16

Your Answer

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

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