Greedy number partitioning

The simplest greedy partitioning algorithm is called list scheduling.

[1] This heuristic can be used as an online algorithm, when the order in which the items arrive cannot be controlled.

An improved greedy algorithm is called LPT scheduling.

It processes the inputs by descending order of value, from large to small.

After sorting the numbers in descending order (as in LPT), it constructs a k-ary tree.

Traversing the tree in depth-first order requires only O(n) space, but might take O(kn) time.

The runtime can be improved by using the greedy heuristic: in each level, develop first the branch in which the current number is put in the set with the smallest sum.

The goal is to partition the items among the people in as fair way as possible.