k-Partition Problem

computation scheduling

Definition

-Partition Problem

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

Instance: a multiset of positive integers and a positive integer .
Question: does there exist a partition of such that

Target sum

If such a partition exists, each part has sum

Hence the instance is immediately infeasible if does not divide .

Special cases

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