Bin Packing with uniform size constraints

Question

Consider the following version of the Bin Packing problem: We are given $k$ unit-size bins and $n$ items with sizes $\epsilon < a_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins?

Here is two simple observations:

• When $\epsilon \le \frac{1}{4}$, this problem is strongly NP hard by a reduction from the 3-partition problem (Garey and Johnson: SP15).
• When $\epsilon \ge \frac{1}{3}$, this problem is in P: place each item with size greater than $\frac{1}{2}$ in a separate bin. Assign maximum number of items left to non-empty bins. Arbitrarily, pair items still unassigned. If the number of these pairs is not more than the number of empty bins, assign these pairs to empty bins. Otherwise, it's impossible to pack the items in $k$ bins. It's not hard to see that you can generalized this even to the case that $\frac{1}{3} \le a_i$.

Is there any complexity result for the case that $\frac{1}{4} < \epsilon < \frac{1}{3}$?

Answer 1

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta>0$, the Bin Packing problem is NP-hard when $1/3-\delta < a_i$ for all $i$.

Answer 2

On the positive side, there is a $\mathsf{OPT} + O(\log n)$ approximation (as opposed to the $\mathsf{OPT} + O(\log^2 n)$ approximation known for general bin-packing): either using the Karmakar-Karp rounding of the Gilmore-Gomory relaxation of bin packing (check David Williamson's book), or, more recently, using the connection with discrepancy of permutations and the $O(\log n)$ constructive upper bound on the discrepancy of 3 permutations of Bohus.