The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson. Its novelty comes from the fact that it uses an algorithm for another famous problem - the bin packing problem - as a subroutine.
The algorithm The input to the algorithm is a set S of numbers, and a parameter n. The required output is a partition of S into n subsets, such that the largest subset sum (also called the makespan) is as small as possible. The algorithm uses as a subroutine, an algorithm called first-fit-decreasing bin packing (FFD). The FFD algorithm takes as input the same set S of numbers, and a bin-capacity c. It heuristically packs numbers into bins such that the sum of numbers in each bin is at most C, aiming to use as few bins as possible. Multifit runs FFD multiple times, each time with a different capacity C, until it finds some C such that FFD with capacity C packs S into at most n bins. To find it, it uses binary search as follows.
Let L := max ( sum(S) / n, max(S) ). Note, with bin-capacity smaller than L, every packing must use more than n bins. Let U := max ( 2 sum(S) / n, max(S) ). Note, with bin-capacity at least U, FFD uses at most n bins. Proof: suppose by contradiction that some input si did not fit into any of the first n bins. Clearly this is possible only if i ≥ n+1. If si > C/2, then, since the inputs are ordered in descending order, the same inequality holds for all the first n+1 inputs in S. This means that sum(S) > (n+1)C/2 > n U/2, a contradiction to the definition of U. Otherwise, si ≤ C/2. So the sum of each of the first n bins is more than C/2. This again implies sum(S) > n C/2 > n U/2, contradiction. Iterate k times (where k is a precision parameter): Let C := (L+U)/2. Run FFD on S with capacity C. If FFD needs at most n bins, then decrease U by letting U := C. If FFD needs more than n bins, then increase L by letting L := C. Finally, run FFD with capacity U. It is guaranteed to use at most n bins. Return the resulting scheduling.
Performance 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. To find this constant, we must first analyze FFD. While the standard analysis of FFD considers approximation w.r.t. number of bins when the capacity is constant, here we need to analyze approximation w.r.t. capacity when the number of bins is constant. Formally, for every input size S and integer n, let O P T ( S , n ) {\displaystyle OPT(S,n)} be the smallest capacity such that S can be packed into n bins of this capacity. Note that O P T ( S , n ) {\displaystyle OPT(S,n)} is the value of the optimal solution to the original scheduling instance. Let r n {\displaystyle r_{n}} be the smallest real number such that, for every input S, FFD with capacity r n ⋅ O P T ( S , n ) {\displaystyle r_{n}\cdot OPT(S,n)} uses at most n bins.
Upper bounds Coffman, Garey and Johnson prove the following upper bounds on r n {\displaystyle r_{n}} :
r n ≤ 8 / 7 ≈ 1.14 {\displaystyle r_{n}\leq 8/7\approx 1.14} for n = 2;
r n ≤ 15 / 13 ≈ 1.15 {\displaystyle r_{n}\leq 15/13\approx 1.15} for n = 3;
r n ≤ 20 / 17 ≈ 1.176 {\displaystyle r_{n}\leq 20/17\approx 1.176} for n = 4,5,6,7;
… excerpt ends here. Continue reading the full article.
