Greedy number partitioning

In computer science, greedy number partitioning is a greedy algorithm for multiway number partitioning. It imitates the way children choose teams for a game. It was first analyzed by Ronald Graham in the 1960s in the context of the multiprocessor scheduling problem.[1][2]:sec.5 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.

Linear-time 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. The algorithm runs in time O(n). It always returns a partition in which the largest sum is at most times the optimal (minimum) largest sum.[1]

Improved algorithm

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 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 times the optimal (maximum) smallest sum.[3] A tighter analysis shows that the ratio is at most , 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 times the optimum almost surely , and in expectation.[5]

Implementation

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

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(nk) 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.

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

References
  1. Graham, Ron L. (1966). "Bounds for Certain Multiprocessing Anomalies". Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. ISSN 1538-7305.
  2. 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.
  3. Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (1982-06-01). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019. ISSN 0196-5212.
  4. Csirik, János; Kellerer, Hans; Woeginger, Gerhard (1992-06-01). "The exact LPT-bound for maximizing the minimum completion time". Operations Research Letters. 11 (5): 281–287. doi:10.1016/0167-6377(92)90004-M. ISSN 0167-6377.
  5. Frenk, J. B. G.; Kan, A. H. G. Rinnooy (1986-06-01). "The rate of convergence to optimality of the LPT rule". Discrete Applied Mathematics. 14 (2): 187–197. doi:10.1016/0166-218X(86)90060-0. ISSN 0166-218X.
  6. Korf, Richard E. (1995-08-20). "From approximate to optimal solutions: a case study of number partitioning". Proceedings of the 14th international joint conference on Artificial intelligence - Volume 1. IJCAI'95. Montreal, Quebec, Canada: Morgan Kaufmann Publishers Inc.: 266–272. ISBN 978-1-55860-363-9.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.