k-Partition Problem

computation scheduling

Definition

$k$-Partition Problem

The $k$-partition problem is a decision problem that asks whether a multiset of positive integers can be divided into $k$ parts with equal sum.

Instance: a multiset $S$ of positive integers and a positive integer $k$.
Question: does there exist a partition $S_1,\dots ,S_k$ of $S$ such that

$$\sum _{x\in S_1}x=\cdots =\sum _{x\in S_k}x?$$

Target sum

If such a partition exists, each part has sum

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

Hence the instance is immediately infeasible if $k$ does not divide ${\sum }_{x\in S}x$.

Special cases

The 3-partition problem is a constrained form in which $|S|=3n$ and the task is to partition $S$ into $n$ triplets of equal sum.