fourpartition

Fourpartition is a decision problem in combinatorial optimization. It asks whether a given multiset of positive integers can be divided into four disjoint subsets that all have the same sum.

Formal definition: Given a finite multiset A = {a1, ..., an} of positive integers with total sum S, does there exist four subsets S1, S2, S3, S4 such that each element of A belongs to exactly one Si and sum(Si) = S/4 for i = 1,2,3,4? If S is not divisible by 4, the answer is no. Elements may repeat, reflecting the multiset nature.

Complexity: The fourpartition problem is NP-complete in the strong sense, as part of the broader class of k-partition problems. This means there is no known polynomial-time algorithm for solving all instances unless P = NP, and the hardness persists even when the numbers are represented in unary. For comparison, the related two-way partition problem is solvable by dynamic programming in pseudo-polynomial time, but fourpartition inherits computational intractability from its higher-arity nature.

Variants and methods: Variants include relaxing the requirement of equal sums or allowing more or fewer than four parts. Exact algorithms include backtracking with pruning, branch-and-bound, and constraint programming; practical solutions often use encodings to SAT or integer linear programming. Heuristic and approximate methods, such as greedy or largest processing time first strategies, can provide quick, feasible partitions for large instances but do not guarantee optimality.

Example: Consider A = {5, 5, 4, 3, 2, 1}, with total sum 20 and target sum per part 5. A valid partition is {5}, {5}, {4,1}, and {3,2}.