5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your special case has only one instance for each value of $n$. No such problem can be NP-hard unless P=NP. $\endgroup$ – Sasho Nikolov Nov 5 '14 at 19:34
  • 2
    $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 6 '14 at 11:52
10
$\begingroup$

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.

$\endgroup$

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.