1BP is (1.5-ε)-inapprox

Dependencies:

  1. Bin packing and Knapsack
  2. Partition problem is NP-complete

For the classical bin packing problem, it is NP-complete to decide if a set of items can be packed into 2 bins. Consequently, for any $\varepsilon > 0$, there is no $(1.5-\varepsilon)$-approx algorithm for classical bin packing unless P=NP.

Proof

Let $A = \{a_1, a_2, \ldots, a_n\}$ be a partition instance. Let $B = \left\{\frac{2a_i}{\operatorname{sum}(A)}: a_i \in A\right\}$.

Then $B$ can be packed in 2 bins iff $A$ can be partitioned into equi-sum sets. This is because a partitioning of $A$ can be used to get a packing of $B$ into 2 bins and a packing of $B$ into 2 bins can be used to get a partition of $A$. Since the partition problem is NP-complete, it is NP-complete to decide whether a set of items can be packed into 2 bins.

If there is a $(1.5-\varepsilon)$-approx algorithm for bin packing, we can use it to decide if $B$ can be packed into 2 bins: the algorithm will output 2 iff $B$ can be packed into 2 bins. Therefore, we cannot have a $(1.5-\varepsilon)$-approx algorithm for bin packing unless P=NP.

Dependency for: None

Info:

Transitive dependencies:

  1. /complexity/np-completeness/3-sat
  2. Bin packing and Knapsack
  3. Subset-sum is NP-complete
  4. Partition problem is NP-complete