<p>As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta&gt;0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta&gt;0$, the Bin Packing problem is NP-hard when $1/3-\delta &lt; a_i$ for all $i$.</p>

CC BY-SA 3.0
2011-06-08T16:00:52.860Z
2011-06-08T16:00:52.860Z
randomizer
<p>On the positive side, there is a $\mathsf{OPT} + O(\log n)$ approximation (as opposed to the $\mathsf{OPT} + O(\log^2 n)$ approximation known for general bin-packing): either using the Karmakar-Karp rounding of the Gilmore-Gomory relaxation of bin packing (check David Williamson's book), or, more recently, using the <a href="http://arxiv.org/abs/1007.2170" rel="nofollow">connection</a> with discrepancy of permutations and the $O(\log n)$ constructive upper bound on the discrepancy of 3 permutations of <a href="http://onlinelibrary.wiley.com/doi/10.1002/rsa.3240010208/abstract" rel="nofollow">Bohus</a>.</p>

CC BY-SA 3.0
2011-06-08T17:41:19.860Z
2011-06-08T18:09:28.533Z
2011-06-08T18:09:28.533Z
Sasho Nikolov
<p>Consider the following version of the Bin Packing problem:
We are given $k$ unit-size bins and $n$ items with sizes $\epsilon &lt; a_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins?</p>

<p>Here is two simple observations:</p>

<ul>
<li>When $\epsilon \le \frac{1}{4}$, this problem is strongly NP hard by a reduction from the <a href="http://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow">3-partition problem</a> (Garey and Johnson: SP15).</li>
<li>When $\epsilon \ge \frac{1}{3}$, this problem is in P: place each item with size greater than $\frac{1}{2}$ in a separate bin. Assign maximum number of items left to non-empty bins. Arbitrarily, pair items still unassigned. If the number of these pairs is not more than the number of empty bins, assign these pairs to empty bins. Otherwise, it's impossible to pack the items in $k$ bins. It's not hard to see that you can generalized this even to the case that $\frac{1}{3} \le a_i$.</li>
</ul>

<p><strong>Is there any complexity result for the case that $\frac{1}{4} &lt; \epsilon &lt; \frac{1}{3}$?</strong>  </p>

CC BY-SA 3.0
2011-06-07T21:53:48.400Z
Why do you need $\epsilon < 1/4$ for the reduction from 3-partition? Won't $\epsilon < 1/3$ work?
Peter Shor 
CC BY-SA 3.0
2011-06-07T22:56:53.690Z
@Peter In the 3-partition problem, items have size between $1/4$ and $1/2$. I am not sure if this problem remains NP-hard when sizes are between $\epsilon$ and $1/2$ for an arbitrary $\epsilon < 1/3$.
randomizer
CC BY-SA 3.0
2011-06-08T00:24:36.857Z
if you go through the proof of 3-partition, I believe that you will discover that it is still NP-hard if the sizes are between $1/3-\delta$ and $1/3+\delta$, for any constant $\delta$.
Peter Shor 
CC BY-SA 3.0
2011-06-08T01:20:24.730Z
@Peter: You are right. I think that by the same trick  used in the proof, adding a big number to the numbers, one can trivially reduce the original 3-partition problem to this version.
randomizer
<cc.complexity-theory><ds.algorithms><packing>
Bin Packing with uniform size constraints
randomizer
# Bin Packing with uniform size constraints

(Asked by: username_0 on 2011-06-07)

Consider the following version of the Bin Packing problem:
We are given $k$ unit-size bins and $n$ items with sizes $\epsilon < a\_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins?

Here is two simple observations:

* When $\epsilon \le \frac{1}{4}$, this problem is strongly NP hard by a reduction from the [3-partition problem](http://en.wikipedia.org/wiki/3-partition_problem) (Garey and Johnson: SP15).
* When $\epsilon \ge \frac{1}{3}$, this problem is in P: place each item with size greater than $\frac{1}{2}$ in a separate bin. Assign maximum number of items left to non-empty bins. Arbitrarily, pair items still unassigned. If the number of these pairs is not more than the number of empty bins, assign these pairs to empty bins. Otherwise, it's impossible to pack the items in $k$ bins. It's not hard to see that you can generalized this even to the case that $\frac{1}{3} \le a\_i$.

**Is there any complexity result for the case that $\frac{1}{4} < \epsilon < \frac{1}{3}$?**

**Tags:** cc.complexity-theory, ds.algorithms, packing

> **Comments:**
> **username_1**: Why do you need $\epsilon < 1/4$ for the reduction from 3-partition? Won't $\epsilon < 1/3$ work?  
> **username_0**: @Peter In the 3-partition problem, items have size between $1/4$ and $1/2$. I am not sure if this problem remains NP-hard when sizes are between $\epsilon$ and $1/2$ for an arbitrary $\epsilon < 1/3$.  
> **username_1**: if you go through the proof of 3-partition, I believe that you will discover that it is still NP-hard if the sizes are between $1/3-\delta$ and $1/3+\delta$, for any constant $\delta$.  
> **username_0**: @Peter: You are right. I think that by the same trick  used in the proof, adding a big number to the numbers, one can trivially reduce the original 3-partition problem to this version.  

---

## 2 answers

### Answer by username_0 on 2011-06-08. Score: 5 | Accepted answer

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta>0$, the Bin Packing problem is NP-hard when $1/3-\delta < a\_i$ for all $i$.


---

### Answer by username_2 on 2011-06-08. Score: 2

On the positive side, there is a $\mathsf{OPT} + O(\log n)$ approximation (as opposed to the $\mathsf{OPT} + O(\log^2 n)$ approximation known for general bin-packing): either using the Karmakar-Karp rounding of the Gilmore-Gomory relaxation of bin packing (check David Williamson's book), or, more recently, using the [connection](http://arxiv.org/abs/1007.2170) with discrepancy of permutations and the $O(\log n)$ constructive upper bound on the discrepancy of 3 permutations of [Bohus](http://onlinelibrary.wiley.com/doi/10.1002/rsa.3240010208/abstract).


---

