Greedy number partitioning

In computer science, greedy number partitioning is a greedy algorithm for multiway number partitioning. It was first analyzed by Ronald Graham in the 1960s in the context of the identical-machines scheduling problem; In this context, it is often called Longest Processing Time (LPT).

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.

Unordered algorithm

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. For example, if the input sequence is S = {4,5,6,7,8} and k=2, then the resulting partition is {4,6,8}, {5,7}; if k=3, then the resulting 3-way partition is {4,7}, {5,8}, {6}.

The algorithm runs in time O(n). It always returns a partition in which the largest sum is at most $2-{\frac {1}{k}}$ times the optimal (minimum) largest sum. This heuristic can be used as an online algorithm, when the order in which the items arrive cannot be controlled.

Ordered algorithm

The standard 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 = {4,5,6,7,8} and k=2, then the resulting partition is {8,5,4}, {7,6}; if k=3, then the resulting 3-way partition is {8}, {7, 4}, {6, 5}.

The running time 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 both sums are equal to 15. However, its suboptimality is bounded both in the worst case and in the average case.

Worst-case maximum sum

In the worst case, the largest sum in the greedy partition is at most ${\frac {4k-1}{3k}}={\frac {4}{3}}-{\frac {1}{3k}}$ times the optimal (minimum) largest sum. In particular, when k =2 this ratio is 7/6.

Worst-case minimum sum

In the worst case, the smallest sum in the returned partition is at least ${\frac {3}{4}}$ times the optimal (maximum) smallest sum. The proof is by contradiction. We consider a minimal counterexample, that is, a counterexample with a smallest k and fewest input numbers. Denote the greedy partition by P₁,...,P_k, and the optimal partition by Q₁,...,Q_k. Some properties of a minimal counterexample are:

• The min-sum in the optimal partition is 4, and the min-sum in the greedy partition is less than 3 (this is just normalization - it is without loss of generality).
• The max-sum in the greedy partition is more than 4 (since the total sum in both partitions is the same, and it is at least 4k).
• If sum(P_i)≥3 for some greedy bin P_i, then P_i is not dominated by any optimal bin Q_j. Proof: if P_i is dominated by Q_j, then we can construct a smaller counterexample by decreasing k to k-1 and removing the items in P_i. The min-sum in the greedy partition remains less than 3. In the optimal partition, the items in P_i can be replaced by their dominating items in Q_j, so the min-sum remains at least 4.
• If sum(P_i)≥3 for some greedy bin P_i, then P_i contains at least two numbers. Proof: if P_i contains only one number x, then it is dominated by the optimal bin Q_j which contains x.givese some input x is at least 3, and the greedy algorithm puts it in some P_i. Then, since there is a bundle with sum less than 3, the greedy algorithm will not put any other input in P_i, contradicting the previous lemma.
• Every greedy bin P_i contains at most one input weakly-larger than 3/2. Proof: Let P_i be the first greedy bin which is assigned two such inputs. Since inputs are assigned in descending order, P_i is the first greedy bin assigned two inputs. This means that it must contain the smallest two inputs from among the largest k+1 inputs. Moreover, since the sum of these two items is at least 3/2+3/2=3, P_i is not assigned any other input. On the other hand, by the pigeonhole principle, there must be some optimal bin Q_j that contains some two inputs from among the largest k+1 inputs; so P_i is dominated by Q_j.
• During the run of the greedy algorithm, the sum in every greedy bin P_i becomes at least 8/3 before the sum of any bin exceeds 4. Proof: Let y be the first input added to some bin P_i, which made its sum larger than 4. Before y was added, P_i had the smallest sum, which by assumption was smaller than 8/3; this means that y>4/3. Let T denote the set of all inputs from the first one down to y; all these inputs are larger than 4/3 too. Since P_i was smaller than 8/3, it contained exactly one item x from T. So now P_i contains exactly 2 items {x,y}, and remains with these 2 items until the algorithm ends. We show that there is some optimal bin Q_j that dominates P_i:
  • If some optimal bin contains 3 or more elements of T, then the sum of any two of them is larger than 8/3, which is larger than x; and the third one is at least y. So it dominates {x,y}.
  • If the optimal bin containing x contains another element of T, then again it dominates {x,y}.
  • If the optimal bin containing x does not contain another element of T, then we have at least 1 optimal bin containing 1 element of T, and the other n-1 optimal bins contain at most 2 items of T. So |T|≤2n-1, and there must be some greedy bin containint at most 1 element of T, say z, whose optimal bin contains another element of T. This z must be at least x, since the algorithm decided to add the item y to x and not to z. Therefore, the optimal bin containing z dominates {z}.
• We can assume, without loss of generality, that all inputs are either smaller than 1/3, or at least 1. Proof: Suppose some input x is in [1/3,1). We replace x with 1. This obviously does not decrease the optimal min-sum. We show that it does not change the greedy min-sum. We know that some greedy bundle P_i has a final sum larger than 4. Before the last input was added into P_i, its sum was smaller than 3; so P_i became larger than 4 when some input larger than 1 was added to it. By the previous lemma, at that point the sum of all other greedy bundles was at least 8/3. The algorithm arrives at x afterwards. Once the algorithm adds x to some bin P_j, the sum of P_j becomes at least 8/3+1/3=3, so no more items are added into P_j. So P_j contains only one input with size in [1/3,1). Once x is replaced with 1, it is still inserted into P_j, and its sum is still above 3. So the greedy min-sum does not change.
• We can now partition the inputs into small (less than 1/3) and large (at least 1). The set of small items in P_i is denoted by S_i.

The proof that a minimal counterexample does not exist uses a weighting scheme. Each input x is assigned a weight w(x) according to its size and greedy bundle P_i:

• If x is a large item:
  • If x is the single large item in P_i, then w(x)=8/3.
  • If there are two large items P_i, x is the largest of them, and sum(P_i)≥3, then w(x)=8/3.
  • Otherwise, w(x)=4/3.
• If x is a small item:
  • if sum(P_i)≥3, then w(x) = 4x/(3 sum(S_i)); so w(S_i) = 4/3.
  • if sum(P_i)<3, then w(x) = 2x/(3 sum(S_i)); so w(S_i) = 2/3.

This weighting scheme has the following properties:

• If x≥2 then w(x)=8/3.
• If x<1/3 then w(x) > 2x.
• The weight of every greedy bin is at most 4, and the weight of at least one greedy bin is at most 10/3. Therefore, the weight of all inputs is at most 4k-2/3.
• The weight of every optimal bin is at least 4. Therefore, the weight of all inputs is at least 4k - a contradiction. Therefore, a counterexample does not exist.

A more sophisticated analysis shows that the ratio is at most ${\frac {3k-1}{4k-2}}$. It is tight. In particular, when k=2 the ratio is 5/6.

Average-case maximum sum

In the average case, if the input numbers are distributed uniformly in [0,1], then the largest sum is $1+O(\log {\log {n}}/n)$ times the optimum almost surely , and $1+O(1/n)$ in expectation.

Implementation

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

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])

An 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, 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 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:

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