# Special case of Bin-packing problem

We know that the decision version of Bin-packing problem is NP-complete: Given an integer B, an integer k, and a list of integers X = (x1, x2, . . . , xn) where xi ∈ [0, B], is there any partition of X into k sublists, such that each sublist sums to at most B?

But what about the special case where the given numbers x_i's are as follows: x_1 = 1, x_2 = 2, ... , x_n = n.

Then is this case also NP-complete?

In general is there any reference that I can find all or many versions of Bin-packing problem, and the facts known about them?

• Your special case has only one instance for each value of $n$. No such problem can be NP-hard unless P=NP. – Sasho Nikolov Nov 5 '14 at 19:34
• @Sasho: the special case actually has kB instances for each value of $n$. But this still isn't enough to make it NP-hard unless P=NP. – Peter Shor Nov 6 '14 at 11:52

## 1 Answer

We wrote a paper related to that. Perfect packing theorems and the average-case behavior of optimal and on-line packing, by Coffman, Courcoubetis, Garey, Johson, Shor, Weber, and Yannakakis. See Theorem 1:

Perfect Packing Theorem: For positive integers k, j, and r, with k ≥ j, one can perfectly pack a list L consisting of rj items, r each of sizes 1 through j, into bins of size k if and only if the sum of the rj item sizes is a multiple of k.

You should note that this only solves the question when (for the OPs definition of $k$ and $n$) $k$ divides $\frac{1}{2}n(n+1)$. If anybody knows how to solve it for all $k$, they should definitely submit another answer.