Greedy number partitioning

The basic algorithm just processes the numbers in an arbitrary order, and iteratively adds the next number to a set in which the current sum is smallest. The algorithm runs in time O(n). 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]

The improved algorithm first sorts the numbers in descending order, and then Iteratively adds the next-largest number to a set in which the current sum is smallest.

For example, if the input set is S = {8,7,6,5,4} and k=2, then the resulting partition is {8,5,4}, {7,6} where the sum-difference is 4. If k=3, then the resulting 3-way partition is {8}, {7, 4}, {6, 5} where the sum-difference is 3.

The runtime complextiy of this algorithm is dominated by the sorting, which takes O(n log n) time.

The algorithm might not find the optimal partition. For example, in the above instance the optimal partition {8,7}, {6,5,4}, where the sum-difference is 0. However, its suboptimality is bounded both in the worst case and in the average case:

• In the worst case, the largest sum in the returned partition is at most ${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}}$ times the optimal (minimum) largest sum.[2]^:sec.5 In particular, when k =2 this ratio is 7/6.
• In the worst case, the smallest sum in the returned partition is at least ${\displaystyle {\frac {3}{4}}}$ times the optimal (maximum) smallest sum.[3] A tighter analysis shows that the ratio is at most ${\displaystyle {\frac {3k-1}{4k-2}}}$, and it is tight.[4] In particular, when k=2 the ratio is 5/6.
• In the average case, if the input numbers are distributed uniformly in [0,1], then the largest sum is ${\displaystyle 1+O(\log {\log {n}}/n)}$ times the optimum almost surely , and ${\displaystyle 1+O(1/n)}$ in expectation.[5]

Below is an example, written in Python, for the greedy algorithm.

def find_partition(numbers):
    """Separate given numbers into two series of equal sum.

    Args:
        numbers: an collection of numbers, for an example a list of integers.

    Returns:
        Two lists of numbers.
    """
    A = []
    B = []
    sum_A = 0
    sum_B = 0
    for n in sorted(numbers, reverse=True):
        if sum_A < sum_B:
           A.append(n)
           sum_A = sum_A + n
        else:
           B.append(n)
           sum_B = sum_B + n
    return (A, B)

Example

>>> find_partition([1, 2, 3, 4, 5])
([4, 3], [5, 2, 1])

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, 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(n^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 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:[6]

• 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.

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 was 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).