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?