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

Question

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

Answer 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$$.