1
$\begingroup$

Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum?

For $k = 2$, this is the well-known Partition problem. For general $k$, this is described on Wikipedia as the "multiway number partitioning" problem, and it's claimed there that this problem is NP-hard for every fixed $k$. However, the reference provided there is not satisfactory because it is about a different problem. I also cannot find this problem in Garey and Johnson's "Computers and Intractability: A Guide to the Theory of NP-Completeness".

Is there a good reference for the NP-hardness of this problem?

$\endgroup$
2

0

Browse other questions tagged or ask your own question.