Reduce Partition to Bin Packing and Locate the 3/2 Barrier

Map an equal-split question onto bins of capacity S/2, trap the optimum in the gap 2 or 3, and read off the absolute inapproximability constant.

Problem

BIN-PACKING receives items $a_1,\ldots,a_m$, a bin capacity $B$, and asks for the smallest number of capacity-$B$ bins holding every item. Reduce PARTITION to it by taking $B=S/2$ with $S=\sum_i a_i$, prove that the produced instances always have optimum $2$ or $3$, and deduce that no polynomial-time algorithm achieves absolute approximation ratio below $3/2$ unless $\mathrm{P}=\mathrm{NP}$. State precisely which ratio the barrier constrains.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm. Distinguish an absolute approximation ratio from an asymptotic one.

Hint 1

With capacity $S/2$ the two bins of a legal two-bin packing have no slack at all.

Hint 2

In a First-Fit packing, any two bins together hold more than $B$.

Hint 3

If the optimum only ever takes the values $2$ and $3$, a ratio strictly below $3/2$ separates them by integrality alone.

Full solution

The reduction. Given a multiset $A=\{a_1,\ldots,a_m\}$ of positive integers with $S=\sum_i a_i$, first dispose of two degenerate cases. If $S$ is odd there is no equal split, and if some $a_i>S/2$ that item cannot lie inside a part of sum $S/2$; in either case output a fixed no-instance. Otherwise output the bin-packing instance with the same items, capacity $B=S/2$, and bin budget $k=2$. Computing $S$ and comparing it against each $a_i$ takes polynomially many binary operations, and no number grows, so the mapping is polynomial.

Correctness. The items total $S=2B$. If $A$ splits into two parts of sum $S/2$, each part is exactly one full bin, so two bins suffice. Conversely, if two bins of capacity $B$ hold items of total $2B$, neither bin can carry less than $B$ without pushing the other above $B$, so each carries exactly $B$ and the two bins exhibit an equal split. Hence

The gap. On every instance the reduction produces, the optimum lies in $\{2,3\}$.

Lower bound: the items total $2B>B$, so one bin never suffices, giving $\mathrm{OPT}\ge2$, with equality exactly when the partition exists.

Upper bound: run First-Fit. Fix two bins $i<j$ of its output and let $x$ be the first item placed in bin $j$. When $x$ was placed, bin $i$ already existed and $x$ did not fit into it, so the contents of bin $i$ at that moment plus $x$ exceeded $B$. Contents never shrink, so the final loads satisfy $\mathrm{load}(i)+\mathrm{load}(j)>B$. If First-Fit used four or more bins, pairing $(1,2)$ and $(3,4)$ would give total load greater than $2B$, contradicting the fact that the items total exactly $2B$. Therefore First-Fit uses at most three bins and $\mathrm{OPT}\le3$.

The barrier. Suppose some polynomial-time algorithm $\mathcal{A}$ has absolute approximation ratio $\rho<3/2$, meaning it outputs at most $\rho\cdot\mathrm{OPT}$ bins on every instance. Run it on a Partition-derived instance. If $\mathrm{OPT}=2$ then $\mathcal{A}$ outputs at most $2\rho<3$ bins; bin counts are integers and no algorithm beats the optimum, so it outputs exactly $2$. If $\mathrm{OPT}=3$ then $\mathcal{A}$ outputs at least $3$. Reading the returned bin count therefore decides PARTITION in polynomial time, and PARTITION is NP-complete, so $\mathrm{P}=\mathrm{NP}$. Contrapositively, unless $\mathrm{P}=\mathrm{NP}$ no polynomial-time algorithm has absolute ratio below $3/2$.

A worked pair. Take $A'=\{3,5,6,11,39,36\}$, the multiset produced by the Subset Sum to Partition reduction. Here $S=100$, $B=50$, and $\{36,3,11\}$ and $\{39,5,6\}$ each sum to $50$, so $\mathrm{OPT}=2$. Change one item, $11\mapsto13$, and $A''=\{3,5,6,13,39,36\}$ has $S=102$, $B=51$, and no subset at all of sum $51$; exhaustive search over every assignment of six items to bins confirms $\mathrm{OPT}=3$. First-Fit in the listed order returns loads $27,39,36$ with pairwise sums $66,63,75$, all above $51$, which is exactly the pairwise property that forbids a fourth bin.

What still beats it. The barrier constrains the absolute ratio and nothing else, and the following coexist with it without contradiction.

• First-Fit uses at most $2\cdot\mathrm{OPT}$ bins, because two bins each at most half full would contradict the pairwise property, so at most one bin is half empty. Its tight asymptotic ratio is $1.7$. It is not a decision procedure: on $A'$ in the listed order it opens three bins although $\mathrm{OPT}=2$.
• First-Fit-Decreasing satisfies $\mathrm{FFD}\le\frac{11}{9}\mathrm{OPT}+\frac69$, and its absolute ratio is exactly $3/2$. It meets the barrier and does not cross it. On $A'$ it does find the optimal packing $\{39,11\}$ and $\{36,6,5,3\}$.
• There is an asymptotic PTAS: for every $\varepsilon>0$ a polynomial-time algorithm packs into $(1+\varepsilon)\mathrm{OPT}+O(1)$ bins. The Karmarkar–Karp algorithm packs into $\mathrm{OPT}+O(\log^2 \mathrm{OPT})$ bins.

Neither asymptotic guarantee contradicts the $3/2$ barrier, because both allow an additive term that dominates precisely on the tiny instances the reduction produces, where $\mathrm{OPT}\in\{2,3\}$. Saying "bin packing cannot be approximated below $3/2$" without the word absolute is therefore false.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length. Check additionally that the degenerate cases $S$ odd and $a_i>S/2$ are answered before the mapping runs, and that every approximation claim names the ratio it constrains.

Common mistakes

• Concluding that bin packing is inapproximable below $3/2$ in the asymptotic sense as well; the asymptotic PTAS and Karmarkar–Karp refute that reading.
• Forgetting the guard $a_i>S/2$, which leaves an item that fits in no bin at all.
• Using $\mathrm{OPT}\ge2$ alone and never proving $\mathrm{OPT}\le3$, which is what makes the gap two-valued.
• Treating First-Fit as a decision procedure for PARTITION because it satisfies $2\cdot\mathrm{OPT}$.

Sources and verification

• Garey-Johnson, SR1 (bin packing)
• Lecture 9 First-Fit questions in data/canonical_questions.json
• Corpus coverage note: lecture 9 asks directly about First-Fit bin packing (CQ-0199, CQ-0211, CQ-0212, CQ-0224); the $3/2$ barrier itself is textbook material and is not stated in the merged summary.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified. Every displayed number was recomputed by brute force before it was written down.

Open in the visualization gallery: Partition → Bin Packing and the 3/2 barrier