Greedy number partitioning

In computer science, greedy number partitioning is a class of greedy algorithms for multiway number partitioning. The input to the algorithm is a set S of numbers, and a parameter k. The required output is a partition of S into k subsets, such that the sums in the subsets are as nearly equal as possible. Greedy algorithms process the numbers sequentially, and insert the next number into a bin in which the sum of numbers is currently smallest.

Approximate algorithms[]

The simplest greedy partitioning algorithm is called list scheduling. It just processes the inputs in any order they arrive. It always returns a partition in which the largest sum is at most ${\displaystyle 2-{\frac {1}{k}}}$ times the optimal (minimum) largest sum.^[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. Since it needs to pre-order the inputs, it can be used only as an offline algorithm. It guarantees that the largest sum is at most ${\displaystyle {\frac {4k-1}{3k}}}$ times the optimal (minimum) largest sum, and the smallest sum is at least ${\displaystyle {\frac {3k-1}{4k-2}}}$ times the optimal (maximum) smallest sum. See LPT scheduling for more details.

Exact algorithm[]

The complete greedy algorithm (CGA) is an exact algorithm, i.e., it always finds an optimal solution. It works in the following way. After sorting the numbers in descending order (as in LPT), it constructs a k-ary tree. Each level corresponds to a number, and each of the k branches corresponds to a different set in which the current number can be put. Traversing the tree in depth-first order requires only O(n) space, but might take O(kⁿ) 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. This algorithm finds the greedy (LPT) solution first, but then proceeds to look for better solutions.

Several additional heuristics can be used in the case k=2 to improve the runtime:^[2]

• In a node in which the current sum-difference is at least the sum of all remaining numbers, the remaining numbers can just be put in the smallest-sum subset.
• If we reach a leaf in which the sum-difference is 0 or 1, then the algorithm can terminate since this is the optimum.
• If the subset sums in the current node are equal, then we can put the current number only in one subset, thus reducing the size of the subtree by half.
• The last number can be assigned only to the subset with the smaller sum.

Generalizations[]

In the fair item allocation problem, there are n items and k people, each of which assigns a possibly different value to each item. The goal is to partition the items among the people in as fair way as possible. The natural generalization of the greedy number partitioning algorithm is the envy-graph algorithm. It guarantees that the allocation is envy-free up to at most one item (EF1). Moreover, if the instance is ordered (- all agents rank the items in the same order), then the outcome is EFX, and guarantees to each agent at least ${\displaystyle {\frac {2n}{3n-1}}}$ of his maximin share. If the items are chores, then a similar algorithm guarantees ${\displaystyle {\frac {4n-1}{3n}}}$ MMS.^[3]

References[]

Further reading[]

• Graham, R. L. (November 1966). "Bounds for certain multiprocessing anomalies". The Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x.