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

  • $\begingroup$ Why do you need $\epsilon < 1/4$ for the reduction from 3-partition? Won't $\epsilon < 1/3$ work? $\endgroup$ – Peter Shor Jun 7 '11 at 21:53
  • $\begingroup$ @Peter In the 3-partition problem, items have size between $1/4$ and $1/2$. I am not sure if this problem remains NP-hard when sizes are between $\epsilon$ and $1/2$ for an arbitrary $\epsilon < 1/3$. $\endgroup$ – Randomizer Jun 7 '11 at 22:56
  • 6
    $\begingroup$ if you go through the proof of 3-partition, I believe that you will discover that it is still NP-hard if the sizes are between $1/3-\delta$ and $1/3+\delta$, for any constant $\delta$. $\endgroup$ – Peter Shor Jun 8 '11 at 0:24
  • $\begingroup$ @Peter: You are right. I think that by the same trick used in the proof, adding a big number to the numbers, one can trivially reduce the original 3-partition problem to this version. $\endgroup$ – Randomizer Jun 8 '11 at 1:20

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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