<p>We wrote a paper related to that. <a href="http://davidsjohnson.net/papers/BP1r.pdf" rel="nofollow">Perfect packing theorems and the average-case behavior of optimal and on-line packing</a>, by Coffman, Courcoubetis, Garey, Johson, Shor, Weber, and Yannakakis.  See Theorem 1:</p>

<blockquote>
  <p><strong>Perfect Packing Theorem:</strong> <em>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.</em></p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2014-11-05T18:26:53.117Z
2014-11-17T03:07:48.397Z
2014-11-17T03:07:48.397Z
Peter Shor 
<p>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?</p>

<p>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.</p>

<p>Then is this case also NP-complete?</p>

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

CC BY-SA 3.0
2014-11-05T19:34:20.940Z
Your special case has only one instance for each value of $n$. No such problem can be NP-hard unless P=NP.
Sasho Nikolov
CC BY-SA 3.0
2014-11-06T11:52:18.900Z
@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 
<cc.complexity-theory>
Special case of Bin-packing problem
user24175
# Special case of Bin-packing problem

(Asked by: username_0 on 2014-11-04)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Your special case has only one instance for each value of $n$. No such problem can be NP-hard unless P=NP.  
> **username_2**: @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.  

---

## 1 answers

### Answer by username_2 on 2014-11-05. Score: 11

We wrote a paper related to that. [Perfect packing theorems and the average-case behavior of optimal and on-line packing](http://davidsjohnson.net/papers/BP1r.pdf), 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.


---

