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 edit

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 $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 ${\frac {4k-1}{3k}}$ times the optimal (minimum) largest sum, and the smallest sum is at least ${\frac {3k-1}{4k-2}}$ times the optimal (maximum) smallest sum. See LPT scheduling for more details.

Complete greedy algorithm edit

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 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 two or more subset sums in the current node are equal, then we can put the current number only in one of these subsets, thus reducing the size of the subtree by at least half.
The last number can be assigned only to the subset with the smaller sum.

Generalizations edit

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 ${\frac {2n}{3n-1}}$ of his maximin share. If the items are chores, then a similar algorithm guarantees ${\frac {4n-1}{3n}}$ MMS.^[3]

Implementations edit

Python: The prtpy library contains implementations of the greedy algorithm and complete greedy algorithm.

References edit

^ Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN 0036-1399.
^ Korf, Richard E. (August 1995). "From approximate to optimal solutions: A case study of number partitioning". In Mellish, Chris S. (ed.). IJCAI'95: Proceedings of the 14th international joint conference on Artificial intelligence. pp. 266–272. ISBN 978-1-55860-363-9.
^ Barman, Siddharth; Krishnamurthy, Sanath Kumar (21 April 2020). "Approximation Algorithms for Maximin Fair Division". ACM Transactions on Economics and Computation. 8 (1): 1–28. arXiv:1703.01851. doi:10.1145/3381525. S2CID 217191332.