PARTITION ≤p BIN-PACKING | Complexity Atlas

The construction

The idea: normalize by half the total. A $\mathrm{BIN\text{-}PACKING}$ input is numbers in $(0,1]$ and a bin count $k$ , asking whether they fit into $k$ bins each summing to $\le1$ . Divide each $a_i$ by half the total and all the numbers sum to exactly $2$ ; then two bins of capacity $1$ suffice iff an equal split exists.

The obstacle: some huge $a_i$ might exceed $1$ after normalizing — an invalid output. But if $2a_i>T$ there is no equal split at all, so in that case a fixed string outside the language can be returned.

Algorithm $R'$ . On input $(a_1,\dots,a_n)$ , natural numbers (w.l.o.g. $a_i>0$ ; zeros may be dropped without changing the answer):

Compute $T\leftarrow\sum_j a_j$ .
If some $i$ has $2a_i>T$ : return $\left(\tfrac34,\tfrac34,\tfrac34,\,2\right)$ .
Otherwise, for each $i$ set $b_i\leftarrow\dfrac{2a_i}{\sum_j a_j}$ , and return $(b_1,\dots,b_n,\,2)$ .

The key property of the output. At step 3, $\sum_{i=1}^{n}b_i=\sum_i\frac{2a_i}{T}=\frac{2}{T}\sum_i a_i=\frac{2}{T}\cdot T=2 ,$ where pulling $\frac2T$ out is legitimate because it is constant, independent of $i$ . Also $b_i>0$ and $b_i\le1$ (since $2a_i\le T$ at this step), so $b_i\in(0,1]$ and the output is valid.

On the representation. The $b_i$ are rationals held as a pair of integers — numerator $2a_i$ , denominator $T$ — each of length $O(m+\log n)$ . A $\mathrm{BIN\text{-}PACKING}$ input need not be integral; the definition speaks of numbers in $(0,1]$ .

Visualization

A′ = {3, 5, 6, 11, 39, 36}S = 100

Item block, height proportional to its value

Correctness — both directions

PARTITION ∈ ⟹ BIN-PACKING ∈

Suppose $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ ; some $I$ has $\sum_{i\in I}a_i=\sum_{i\notin I}a_i=T/2$ .

The algorithm reached step 3. Suppose not, i.e. some $i_0$ has $2a_{i_0}>T$ . The side containing $a_{i_0}$ sums to at least $a_{i_0}>T/2$ — contradicting that both sides sum to exactly $T/2$ . So the algorithm did reach step 3.

The packing. Put $\{b_i\}_{i\in I}$ in the first bin and $\{b_i\}_{i\notin I}$ in the second. The first bin sums to $\sum_{i\in I}b_i=\frac{2}{T}\sum_{i\in I}a_i=\frac{2}{T}\cdot\frac{T}{2}=1\;\le\;1 ,$ and likewise the second. Both bins respect the capacity and exactly $2$ bins were used. So $(b_1,\dots,b_n,2)\in\mathrm{BIN\text{-}PACKING}$ .

BIN-PACKING ∈ ⟹ PARTITION ∈

Suppose the output is in $\mathrm{BIN\text{-}PACKING}$ .

Case 1: the algorithm stopped at step 2. Then the output is $\left(\tfrac34,\tfrac34,\tfrac34,2\right)$ . Three items of size $\tfrac34$ do not fit into two bins of capacity $1$ : each bin holds at most one (since $\tfrac34+\tfrac34=\tfrac32>1$ ), so at least $3$ bins are needed. So the output is not in $\mathrm{BIN\text{-}PACKING}$ — contradicting the hypothesis. So this case cannot occur and the algorithm reached step 3.

Case 2: the algorithm reached step 3. Then $b_1,\dots,b_n$ pack into two bins, each summing to $\le1$ . Let $I$ index those in the first bin. Then $\sum_{i\in I}b_i\le1\qquad\text{and}\qquad\sum_{i\notin I}b_i\le1 .$ But all the $b_i$ sum to exactly $2$ , so $\sum_{i\in I}b_i=2-\sum_{i\notin I}b_i\;\ge\;2-1=1 .$ The two inequalities give $\sum_{i\in I}b_i=1$ exactly, and likewise $\sum_{i\notin I}b_i=1$ .

Translate back: $\sum_{i\in I}\frac{2a_i}{T}=1$ , i.e. $\sum_{i\in I}a_i=\frac{T}{2}$ , and hence $\sum_{i\notin I}a_i=T-\frac T2=\frac T2$ . The two sides are equal, so $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ .

Cost of the reduction

TimeO(|x|²)

SpaceO(|x|)

Output sizeO(|x|)

Computing $T$ costs $O(n(m+\log n))$ ; step 2 is $n$ comparisons; step 3 is $n$ writes of the pair $(2a_i,T)$ — no actual division is needed. Total $O(|x|^2)$ , with output length $O(|x|)$ .

What it buys

$\mathrm{BIN\text{-}PACKING}$ is NP-hard — and the same proof gives a bonus: the output always uses $k=2$ , so the problem stays NP-hard with a constant bin count. This is also the starting point for the inapproximability bound: an absolute approximation ratio better than $3/2$ would distinguish $\mathrm{OPT}=2$ from $\mathrm{OPT}=3$ and hence decide $\mathrm{PARTITION}$ .

Pitfalls

The test in step 2 must be $>$ , not $\ge$ . If $a_i=T/2$ exactly, then $\{i\}$ against its complement is a legal split and the input is in $\mathrm{PARTITION}$ — while the step-2 output is not in $\mathrm{BIN\text{-}PACKING}$ , and the reduction would break. With $>$ everything holds, and the boundary case gives $b_i=1$ , a legal value.
Why from $\mathrm{PARTITION}$ rather than $\mathrm{SUBSET\text{-}SUM}$ . The nearest-problem principle again: $\mathrm{PARTITION}$ has no external target, and neither does $\mathrm{BIN\text{-}PACKING}$ — the capacity is dictated internally. Starting from $\mathrm{SUBSET\text{-}SUM}$ would mean baking $S$ in all over again, work already done.

The chain

Rests on

SUBSET-SUM ≤p PARTITION

Used later by

PARTITION ≤p BIN-PACKING-OPT

Where this was read from

Lesson 12משפט 4: $\mathrm{PARTITION} \le_p \mathrm{BIN\text{-}PACKING}$
Guided exercisebin-packing-approximation
2026"In this question we prove the $Bin\text{-}Packing$ problem seen in class is $NP$ -complete."