Multifit algorithm

The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of multiprocessor scheduling with identical processors. It was developed by Coffman, Garey and Johnson.[1]

The algorithm

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 largest subset sum (also called the makespan) in as small as possible.

The algorithm performs a binary search to find the minimum bin capacity for which a certain algorithm for the bin packing problem finds a feasible solution.

Analysis

Multifit is a constant-factor approximation algorithm. It always finds a partition in which the makespan is at most a constant factor larger than the optimal makespan. The constant factor for small values of k is:[1]

  • 8 / 7 ≈ 1.14 for k = 2;
  • 15 / 13 ≈ 1.15 for k = 3;
  • 20 / 17 ≈ 1.176 for k = 4,5,6,7.

For general k, it was proved that the upper bound is 1.220.[1] It was later improved to 6/5=1.2,[2] and later to 13/11≈1.182.[3] This is almost tight: there is an instance with k=13 in which the approximation ratio is exactly 13/11.[2]

References
  1. Coffman, Jr., E. G.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.
  2. Friesen, Donald K. (1984-02-01). "Tighter Bounds for the Multifit Processor Scheduling Algorithm". SIAM Journal on Computing. 13 (1): 170–181. doi:10.1137/0213013. ISSN 0097-5397.
  3. Yue, Minyi (1990-12-01). "On the exact upper bound for the multifit processor scheduling algorithm". Annals of Operations Research. 24 (1): 233–259. doi:10.1007/BF02216826. ISSN 1572-9338.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.