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 (also called the makespan) in 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.

1. Let L := max ( sum(S) / n, max(S) ). Note, with bin-capacity smaller than L, every packing must use more than n bins.
2. 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 s_i did not fit into any of the first n bins. Clearly this is possible only if i ≥ n+1. If s_i > 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, s_i ≤ 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.
3. 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.
4. 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 $OPT(S,n)$ be the smallest capacity such that S can be packed into n bins of this capacity. Note that $OPT(S,n)$ is the value of the optimal solution to the original scheduling instance.

Let $r_{n}$ be the smallest real number such that, for every input S, FFD with capacity $r_{n}\cdot OPT(S,n)$ uses at most n bins. Coffman, Garey and Johnson prove the following upper bounds on $r_{n}$:

• $r_{n}\leq 8/7\approx 1.14$ for n = 2;
• $r_{n}\leq 15/13\approx 1.15$ for n = 3;
• $r_{n}\leq 20/17\approx 1.176$ for n = 4,5,6,7;
• $r_{n}\leq 122/100=1.22$ 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, $L<r_{n}\cdot OPT(S,n)$. Initially, the difference $U-L$ is at most sum(S) / n, which is at most $OPT(S,n)$. After the MultiFit algorithm runs for k iterations, the difference shrinks k times by half, so $U-L\leq (1/2)^{k}\cdot OPT(S,n)$. Therefore, $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$. Therefore, the scheduling returned by MultiFit has makespan at most $r_{n}+(1/2)^{k}$ times the optimal makespan. When $k$ is sufficiently large, the approximation factor of MultiFit can be made arbitrarily close to $r_{n}$, 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.

Proof idea

Minimal counterexamples

The upper bounds on $r_{n}$ are proved by contradiction. For any integers p ≥ q, if $r_{n}>p/q$, then there exists a (p/q)-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 (p/q)-counterexample, which is a (p/q)-counterexample with a smallest number of items in S and a smallest number of bins n. In a minimal (p/q)-counterexample, FFD packs all items in S except the last (smallest) one into n bins with capacity p. Given a minimal (p/q)-counterexample, denote by P₁,...,P_n the (incomplete) FFD packing into these n bins with capacity p, and by Q₁,...,Q_n the (complete) optimal packing into n bins with capacity q. The following lemmas can be proved:

• No union of k subsets from Q_i is dominated by a union of k subsets from P_i ("dominated" means that each item in the dominated subset is mapped to a weakly-larger item in the dominating subset). Otherwise, by deleting the items in the P_i , we could get a smaller counterexample.
• Each Q_i contains at least 3 items. Otherwise we had domination and, by the previous lemma, could get a smaller counterexample.
• Each P_i (except the last one) contains at least 2 items. This is because, if some P_i contains only a single item, this implies that the last (smallest) 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 $s>{\frac {n}{n-1}}(p-q)$. Proof: Since s does not fit into the first n bundles, we have $sum(P_{i})+s>p$, so $\sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p$. On the other hand, since all items fit into n bins of capacity q, we have $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$. Subtracting the inequalities gives $s>{\frac {n}{n-1}}(p-q)$.
• The size of every item is at most $q-2s$. This is because there are at least 3 items in each optimal bin (with capacity q).

Loose upper bound

From the above lemmas, it is already possible to prove a loose upper bound $r_{n}\leq 5/4=1.25$. Proof. Let S, n be a minimal (5/4)-counterexample.

• The above lemmas imply that $s>{\frac {n}{n-1}}(5-4)>1$. Since the optimal capacity is 4, no optimal bin can contain 4 or more items. Therefore, each optimal bin must contain exactly 3 items.
• The above lemmas also imply that the size of each item is at most $4-2s$. Therefore, if FFD generates a bin with only two items, its sum is at most $8-4s<5-s$, so the smallest item can fit into it - a contradiction. Therefore, FFD also packs at least 3 items into each bin. But this means that FFD yields exactly n bins - a contradiction.

Tighter upper bounds

To prove tighter bounds, one needs to take a closer look at the FFD packing of the minimal (p/q)-counterexample. The items and FFD bins P₁,...,P_n are termed as follows:

• A regular item is an item added to some bin, before the next bin was opened. Equivalently, a regular item is at least as large as every item in every next bin.
• A fallback item is an item added to some bin, after the next bin was opened. Equivalently, a fallback item is smaller than the largest item in the next bin.
• A regular k-bin is a bin that contains k regular items and no fallback items.
• A falllback k-bin is a bin that contains k regular items and some fallback items.

In every k-bin, the sum of the k regular items is larger than ${\frac {k}{k+1}}\cdot p$, since otherwise we could add another item before opening a new bin.

Note that, in a minimal counterexample, there are no regular 1-bins (since each bin contains at least 2 items). It can be proved that the FFD bins P₁,...,P_n are ordered by type:

• Zero or more fallback 1-bins;
• Then, zero or more regular 2-bins;
• Then, zero or more fallback 2-bins;
• Then, zero or more regular 3-bins;
• Then, zero or more fallback 3-bins;
• and so on.

The upper bound $r_{n}\leq 1.22$ is proved by assuming a minimal (122/100)-counterexample, analyzing the sizes of items in the different types of FFD bundles, and deriving a contradiction.