View source for Greedy number partitioning

{{Short description|Class of greedy algorithms for multiway number partitioning}}
In [[computer science]], '''greedy number partitioning''' is a class of [[greedy algorithm]]s 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 <math>2-\frac{1}{k}</math> times the optimal (minimum) largest sum.<ref name=":12">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1969-03-01|title=Bounds on Multiprocessing Timing Anomalies|url=https://epubs.siam.org/doi/abs/10.1137/0117039|journal=SIAM Journal on Applied Mathematics|volume=17|issue=2|pages=416–429|doi=10.1137/0117039|issn=0036-1399}}</ref> 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 [[Longest-processing-time-first scheduling|'''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 <math>\frac{4 k-1}{3 k}</math> times the optimal (minimum) largest sum, and the smallest sum is at least  <math>\frac{3k-1}{4k-2}</math> times the optimal (maximum) smallest sum. See [[LPT scheduling]] for more details.

== Complete greedy algorithm {{anchor|CGA}} ==
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 search|depth-first]] order requires only O(''n'') space, but might take O(''k<sup>n</sup>'') 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:<ref name=":0">{{cite book |chapter-url=https://dl.acm.org/doi/abs/10.5555/1625855.1625890 |isbn=978-1-55860-363-9 |chapter=From approximate to optimal solutions: A case study of number partitioning |title=IJCAI'95: Proceedings of the 14th international joint conference on Artificial intelligence |date=August 1995 |pages=266–272 |editor1-first=Chris S. |editor1-last=Mellish |first1=Richard E. |last1=Korf }}</ref>

* 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 ==
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 procedure|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 <math>\frac{2n}{3n-1}</math> of his [[maximin share]]. If the items are ''chores'', then a similar algorithm guarantees <math>\frac{4n-1}{3n}</math> MMS.<ref name=":3">{{cite journal |last1=Barman |first1=Siddharth |last2=Krishnamurthy |first2=Sanath Kumar |title=Approximation Algorithms for Maximin Fair Division |journal=ACM Transactions on Economics and Computation |date=21 April 2020 |volume=8 |issue=1 |pages=1–28 |doi=10.1145/3381525 |arxiv=1703.01851 |s2cid=217191332 }}</ref>

== Implementations ==

* '''Python''': The [https://github.com/erelsgl/prtpy prtpy library] contains implementations of the [https://github.com/erelsgl/prtpy/blob/main/prtpy/partitioning/greedy.py greedy algorithm] and [https://github.com/erelsgl/prtpy/blob/main/prtpy/partitioning/complete_greedy.py complete greedy algorithm].

== References ==
{{reflist}}

==Further reading==
* {{cite journal |last1=Graham |first1=R. L. |title=Bounds for certain multiprocessing anomalies |journal=The Bell System Technical Journal |date=November 1966 |volume=45 |issue=9 |pages=1563–1581 |doi=10.1002/j.1538-7305.1966.tb01709.x }}

[[Category:Number partitioning]]
[[Category:Greedy algorithms]]