Multifit algorithm


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 is as small as possible.
The algorithm uses as a subroutine, an algorithm called first-fit-decreasing bin packing. 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.
  1. Let L := max / n, max. Note, with bin-capacity smaller than L, every packing must use more than n bins.
  2. Let U := max / n, max. 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 > 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 > n C/2 > n ''U/2, contradiction.
  3. Iterate k'' times :
  4. * Let C := /2. Run FFD on S with capacity C.
  5. ** If FFD needs at most n bins, then decrease U by letting U := C.
  6. ** If FFD needs more than n bins, then increase L by letting L := C.
  7. 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 / 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: see lower bound below.

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
  • 6,5,5
  • 4,4,4,4
  • 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.
For n=13: the following shows that, which is tight. The inputs can be packed into 13 bins of capacity 66 as follows:
  • 40,13,13
  • 25,25,16
  • 25,24,17
But if we run FFD with bin capacity smaller than 66*13/11 = 78, then the filled bins are:
  • 40,25
  • 24, 24, 17
  • 17, 16, 16, 16
  • 13, 13, 13, 13, 13
  • 13
Note that the sum in each of the first 13 bins is 65, so we cannot put another 13 inside it. Therefore, 13 bins are not sufficient.

Performance with uniform machines

MultiFit can also be used in the more general setting called uniform-machines scheduling, where machines may have different processing speeds. When there are two uniform machines, the approximation factor is. When MultiFit is combined with the LPT algorithm, the ratio improves to.

Performance for maximizing the smallest sum

A dual goal to minimizing the largest sum is maximizing the smallest sum. Deuermeyer, Friesen and Langston claim that MultiFit does not have a good approximation factor for this problem:
"In the solution of the makespan problem using MULTIFIT, it is easy to construct examples where one processor is never used. Such a solution is tolerable for the makespan problem, but is totally unacceptable for our problem . Modifications of MULTIFIT can be devised which would be more suitable for our problem, but we could find none which produces a better worst-case bound than that of LPT."

Proof idea

Minimal counterexamples

The upper bounds on are proved by contradiction. For any integers p ≥ q, if, then there exists a -counterexample, defined as an instance S and a number n of bins such that
  • S can be packed into n bins with capacity q;
  • FFD does not manage to pack S into n bins with capacity p.
If there exists such a counterexample, then there also exists a minimal -counterexample, which is a -counterexample with a smallest number of items in S and a smallest number of bins n. In a minimal '-counterexample, FFD packs all items in S except the last one into n bins with capacity p. Given a minimal '-counterexample, denote by P1,...,Pn the FFD packing into these n bins with capacity p, by Pn+1 the bin containing the single smallest item, and by Q1,...,Qn the optimal packing into n bins with capacity q. The following lemmas can be proved:
  • No union of k subsets from is dominated by a union of k subsets from . Otherwise we could get a smaller counterexample as follows. Delete all items in the Pi. Clearly, the incomplete FFD packing now needs n-''k bins, and still the smallest item remains unpacked. In the optimal packing Qi, exchange each item with its dominating item. Now, the k'' subsets Qi are larger, but all other n-''k subsets are smaller. Therefore, after deleting all items in the Pi, the remaining items can be packed into at most n''-k bins of size q.
  • Each of Q1,...,Qn contains at least 3 items. Otherwise we had domination and, by the previous lemma, could get a smaller counterexample. This is because each Qi with a single item is dominated by the Pj that contains that item; for each Qi with two items x and y, if both x and y are in the same Pj, then Qi is dominated by this Pj; Suppose x≥y, x is in some Pj, and y is in some Pk to its right. This means that y did not fit into Pj. But x+y ≤ q. This means that Pj must contain some item z ≥ y. So Qi is dominated by Pj. Suppose x≥y, x is in some Pj, and y is in some Pk to its left. This means that there must be a previous item z ≥ x. So Qi is dominated by Pk.
  • Each of P1,...,Pn contains at least 2 items. This is because, if some Pi contains only a single item, this implies that the last item does not fit into it. This means that this single item must be alone in an optimal bundle, contradicting the previous lemma.
  • Let s be the size of the smallest item. Then. Proof: Since s does not fit into the first n bundles, we have, so. On the other hand, since all items fit into n bins of capacity q, we have. Subtracting the inequalities gives.
  • The size of every item is at most. This is because there are at least 3 items in each optimal bin.
  • The sum of items in every bin P1,...,Pn is larger than ; otherwise we could add the smallest item.

    5/4 Upper bound

From the above lemmas, it is already possible to prove a loose upper bound. Proof. Let S, n be a minimal -counterexample. The above lemmas imply that -
  • . Since the optimal capacity is 4, no optimal bin can contain 4 or more items. Therefore, each optimal bin must contain at most 3 items, and the number of items is at most 3n.
  • The size of each item is at most, and the size of each FFD bin is more than. If some FFD bin contained only two items, its sum would be at most ; so each FFD bin must contain at least 3 items. But this means that FFD yields exactly n bins - a contradiction.