# How to give an upper bound on this bin packing problem?

In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set $\{1,\ldots,n\}$. (We assum that $w_i\le f_i$.) Also, we have a set of bins of infinite capacity (each) in which we want to place the objects.

The objective is to assign the objects to the minimum number of bins such that the sum of the weights in each bin is at most the minimum fragility. That is, if we assign the set of objects $S$ to bin $B$ than we must have:

$$\sum_{i\in S}w_i\le\min\limits_{i\in S}f_i.\quad\quad\quad (1)$$

The BPFO problem is given in this paper. Let us denote the optimal value of BPFO by $OPT$.

I am trying to relax BPFO by modifying equation$~(1)$ as follows.

$$\sum_{i\in S}w_i\le f_i,\forall i\in S$$

Let us denote the optimal value of the relaxed problem by $OPTR$.

Now, I would like to upper bound $OPT$ by $OPTR$. How can I achieve this?

It is clear that a solution to BPFO is a solution to the relaxed problem and then $OPT\ge OPTR$.

Is there a way to say that $OPT\le \alpha(n)OPTR$ where $\alpha(n)\ge 1$ ?

Your relaxation is same as original problem.

$$\sum_{i\in S}w_i\leq f_j,\forall j\in S$$

is same condition as

$$\sum_{i\in S}w_i\leq\min\limits_{j\in S}f_j$$.

because

$$\min\limits_{i\in S}f_i \leq f_j,\forall j\in S$$.

• A solution to the original problem implies a solution to the relaxed problem but a solution to the relaxed problem does not imply a solution to the original problem. Am I confusing? Are you saying that both problems are the same? – drzbir Mar 23 '16 at 1:46
• Yes, $Z < x_1$ and $Z < x_2$ if and only if $Z < \min(x_1,x_2)$. – Shreesh Mar 23 '16 at 1:48
• So, $OPTR=OPT$? – drzbir Mar 23 '16 at 1:53
• Yes, that is exact. – Shreesh Mar 23 '16 at 1:59