3-Partition Problem

computation scheduling

Definition

3-Partition Problem

The 3-partition problem is a strongly NP-hard decision problem that asks whether a multiset of $3n$ positive integers can be partitioned into $n$ triplets with equal sum.

Instance: a multiset $S$ of $3n$ positive integers, where $n\in {\mathbb{Z}}^{+}$.
Question: can $S$ be partitioned into sets $S_1,\dots ,S_n$ such that

$$|S_i|=3\text{and}\sum _{x\in S_i}x=T\text{for all }i=1,\dots ,n?$$

where

$$T=\frac{1}{n}\sum _{x\in S}x.$$

Relation

The 3-partition problem is a specialised k-partition problem. Here the number of parts is $n$, and each part must contain exactly three integers.

First compute the target sum per part. Since all $3n$ integers must be used and there must be $n$ equal-sum parts, each part must have sum

$$T=\frac{1}{n}\sum _{x\in S}x.$$

Thus $T$ is not an additional input value. It is the only possible sum of each part if an equal partition exists.

The standard hard version restricts every integer $x\in S$ to lie strictly between one quarter and one half of this target:

$$\frac{T}{4}<x<\frac{T}{2}.$$

These bounds force the number of integers in each part.

One integer cannot form a part, because every integer is smaller than $T$.

Two integers cannot form a part either. If $x,y\in S$, then

$$x+y<\frac{T}{2}+\frac{T}{2}=T.$$

So one or two integers are always too small to reach the required part sum $T$.

Four integers cannot form a part. If $w,x,y,z\in S$, then

$$w+x+y+z>4\cdot \frac{T}{4}=T.$$

So four integers are already too large, and any larger group is too large as well.

A valid part must therefore contain neither fewer than three nor more than three integers. It must contain exactly three integers. This is why the equal-sum condition plus the bounds already force triplets.

Strong NP-Hardness

3-partition is strongly NP-hard, even under the restriction

$$\frac{T}{4}<x<\frac{T}{2}\text{for every }x\in S.$$

This makes 3-partition useful for reductions to scheduling problems. The bounds force each target block of size $T$ to contain exactly three jobs or items, so the reduction can encode grouping rather than only numerical summation.