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 be the smallest capacity such that S can be packed into n bins of this capacity. Note that is the value of the optimal solution to the original scheduling instance.
Let be the smallest real number such that, for every input S, FFD with capacity uses at most n bins.
Upper bounds
Coffman, Garey and Johnson prove the following upper bounds on :
for n = 2; for n = 3; for n = 4,5,6,7; for all n ≥ 8.
During the MultiFit algorithm, the lower bound L is always a capacity for which it is impossible to pack S into n bins. Therefore, . Initially, the difference is at most sum(S) / n, which is at most . After the MultiFit algorithm runs for k iterations, the difference shrinks k times by half, so . Therefore, . Therefore, the scheduling returned by MultiFit has makespan at most times the optimal makespan. When is sufficiently large, the approximation factor of MultiFit can be made arbitrarily close to , which is at most 1.22.
Later papers performed a more detailed analysis of MultiFit, and proved that its approximation ratio is at most 6/5=1.2, and later, at most 13/11≈1.182. The original proof of this missed some cases; presented a complete and simpler proof. The 13/11 cannot be improved: there is an instance with n=13 in which the approximation ratio is exactly 13/11.
Lower bounds
For n=4: the following shows that , which is tight. The inputs are 9,7,6,5,5, 4,4,4,4,4,4,4,4,4. They can be packed into 4 bins of capacity 17 as follows:
9, 4, 4
7, 6, 4
5, 4, 4, 4
5, 4, 4, 4
But if we run FFD with bin capacity smaller than 20, then the filled bins are:
9,7 [4 does not fit]
6,5,5 [4 does not fit]
4,4,4,4 [4 does not fit]
4,4,4,4
4
Note that the sum in each of the first 4 bins is 16, so we cannot put another 4 inside it. Therefore, 4 bins are not sufficient.