# 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

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.