PARTITION ≤p BIN-PACKING-OPT

The construction

Where the $3/2$ comes from. The reduction $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ produces an instance whose items sum to exactly $2$ , each in $(0,1]$ . On such an instance:

$\mathrm{OPT}\ge2$ always, since bin capacity is $1$ and the items total $2$ , so two bins is the least possible;
$\mathrm{OPT}=2$ if and only if an equal split exists — i.e. iff the original instance is in $\mathrm{PARTITION}$ ;
otherwise $\mathrm{OPT}\ge3$ .

So the optimum takes only one of two values, $2$ or $3$ , and telling them apart is equivalent to deciding $\mathrm{PARTITION}$ . This is a classical "gap": the intermediate values are empty.

The algorithm. Suppose for contradiction an approximation $A$ exists with absolute ratio $\rho<\tfrac32$ . Build a decider for $\mathrm{PARTITION}$ :

On input $(a_1,\dots,a_n)$ , run the reduction $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ to get an instance $(b_1,\dots,b_n)$ summing to $2$ .
Run $A$ on it, obtaining a bin count $\mathrm{ALG}$ .
If $\mathrm{ALG}\le2$ — accept; otherwise — reject.

Visualization

bᵢ = 2aᵢ/S · Σbᵢ = 2 · bᵢ ∈ (0,1] · capacity 1

Normalized item bᵢBin capacity 1

Correctness — both directions

PARTITION ∈ ⟹ BIN-PACKING-OPT ∈

Suppose $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ . By correctness of the reduction the constructed instance packs into two bins, i.e. $\mathrm{OPT}=2$ .

Since $A$ is a $\rho$ -approximation for a minimization problem, $\mathrm{ALG}\;\le\;\rho\cdot\mathrm{OPT}\;=\;2\rho\;<\;2\cdot\tfrac32\;=\;3 .$ The bin count is an integer, and $\mathrm{ALG}<3$ forces $\mathrm{ALG}\le2$ . So step 3 accepts.

This is where integrality of the bin count does all the work: the gap between $2$ and $3$ cannot be bridged by an intermediate value.

BIN-PACKING-OPT ∈ ⟹ PARTITION ∈

Suppose $(a_1,\dots,a_n)\notin\mathrm{PARTITION}$ . By correctness of the reduction the constructed instance does not pack into two bins, and since $\mathrm{OPT}\ge2$ always, $\mathrm{OPT}\ge3$ .

An approximation algorithm returns a feasible solution, i.e. a legal packing, and a legal packing cannot use fewer bins than the optimum. So $\mathrm{ALG}\;\ge\;\mathrm{OPT}\;\ge\;3\;>\;2 ,$ and step 3 rejects.

Conclusion. The algorithm decides $\mathrm{PARTITION}$ in polynomial time (the reduction is polynomial, $A$ is polynomial by definition, the comparison is constant). But $\mathrm{PARTITION}$ is NP-hard, so $\mathrm{NP}\subseteq\mathrm{P}$ , i.e. $\mathrm{P}=\mathrm{NP}$ .

Cost of the reduction

TimeO(|x|²) plus one call to A

SpaceO(|x|)

Output sizeO(|x|)

The cost is exactly that of the reduction $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ ( $O(|x|^2)$ ), plus a single call to $A$ and one comparison.

What it buys

No polynomial algorithm for bin packing achieves an absolute ratio better than $\tfrac32$ , unless $\mathrm{P}=\mathrm{NP}$ . Note this does not contradict the First-Fit algorithm at ratio $2$ , nor asymptotic approximation schemes — the result bounds the absolute ratio only, and that distinction is the whole point.

Pitfalls

Absolute versus asymptotic ratio. The result rests entirely on instances with $\mathrm{OPT}\in\{2,3\}$ — small numbers. An asymptotic ratio concerns behaviour as $\mathrm{OPT}\to\infty$ , where this bound says nothing. Conflating the two is the standard mistake on this question.
Integrality of the bin count is the critical step. $\mathrm{ALG}<3$ forces $\mathrm{ALG}\le2$ only because bin counts are integers. For a minimization problem with continuous values the same argument would fail — which is why this barrier belongs specifically to bin packing.

The chain

Rests on

PARTITION ≤p BIN-PACKING

Where this was read from

Lesson 25תרגיל 7: קירוב $1.49$ ל- $\mathrm{BIN\text{-}PACKING}$ גורר $\mathrm{P}=\mathrm{NP}$
Lesson 12משפט 5 (בונוס של אותה הוכחה): $\mathrm{BIN\text{-}PACKING}$ נשארת NP-hard גם כאשר $k=2$ קבוע
Guided exercisebin-packing-approximation