# combinatorics – Can this special case of bin packing be solved in polynomial time?

Consider a set of $$n$$ integers, where each integer is between $$1$$ and $$3 M$$. The sum of all integers is $$3 S$$. There are three bins. The capacity of each bin is $$C = S + M$$.
Is there a polynomial-time algorithm to decide whether all integers can be packed into the bins?

To explain why this specific case is special, consider some variants of the problem:

• When $$C$$ is not fixed, the problem is NP-hard, since it is a special case of the bin-packing problem.
• When $$C = S$$, the problem is NP-hard, since it is equivalent to 3-way number partitioning.
• When $$C geq S + 2 M$$, the problem is easy since the answer is always “yes”. Proof: put the agents in an arbitrary order into the bins as long as there is room. Suppose by contradiction that not all integers are packed; let $$x$$ be some remaining integer. Then the sum in each bin is larger than $$C-x$$, so the sum in all bins is more than $$3 C – 3 x geq 3 S + 6 M – 3 x$$.
Since $$x leq 3 M$$, this sum is larger than $$3 S + 2 x – 3 x = 3 S – x$$. But then the sum of all integers plus $$x$$ is larger than $$3 S$$ – a contradiction.

The case $$C = S+M$$ is between these extremes: it is larger than $$S$$ for which the problem is hard, but smaller than $$S+2M$$ for which the answer is always yes.

Is this case is easy or hard?