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.
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.
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.
is the value of the optimal solution to the original scheduling instance.
be the smallest real number such that, for every input S, FFD with capacity
Coffman, Garey and Johnson prove the following upper bounds on
:[1] During the MultiFit algorithm, the lower bound L is always a capacity for which it is impossible to pack S into n bins.
After the MultiFit algorithm runs for k iterations, the difference shrinks k times by half, so
is sufficiently large, the approximation factor of MultiFit can be made arbitrarily close to
Later papers performed a more detailed analysis of MultiFit, and proved that its approximation ratio is at most 6/5=1.2,[2] and later, at most 13/11≈1.182.
MultiFit can also be used in the more general setting called uniform-machines scheduling, where machines may have different processing speeds.
When MultiFit is combined with the LPT algorithm, the ratio improves to
Deuermeyer, Friesen and Langston claim that MultiFit does not have a good approximation factor for this problem:[7]"In the solution of the makespan problem using MULTIFIT, it is easy to construct examples where one processor is never used.
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.
, then there exists a (p/q)-counterexample, defined as an instance S and a number n of bins such that 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 P1,...,Pn the (incomplete) FFD packing into these n bins with capacity p, by Pn+1 the bin containing the single smallest item, and by Q1,...,Qn the (complete) optimal packing into n bins with capacity q.
The above lemmas imply that - To prove tighter bounds, one needs to take a closer look at the FFD packing of the minimal (p/q)-counterexample.
In a minimal counterexample, there are no regular 1-bins (since each bin contains at least 2 items), so by the above lemmas, the FFD bins P1,...,Pn are ordered by type: The upper bound
Each item is given a weight based on its size and its bin in the FFD packing.
The items are assigned types and weights as follows.
Still, the total weight of items in every FFD bin is at least 100-D: The total weight of items in most optimal bins is at most 100-D: The upper bound
[3] is proved by assuming a minimal ((120-3d)/100)-counterexample, with some d<20/33, and deriving a contradiction.
MultiFit is not monotone in the following sense: it is possible that an input decreases while the max-sum in the partition returned by MultiFit increases.
As an example,[1]: Fig.4 suppose n=3 and the input numbers are:44, 24, 24, 22, 21, 17, 8, 8, 6, 6.FFD packs these inputs into 3 bins of capacity 60 (which is optimal): But if the "17" becomes "16", then FFD with capacity 60 needs 4 bins: so MultiFit must increase the capacity, for example, to 62: This is in contrast to other number partitioning algorithms - List scheduling and Longest-processing-time-first scheduling - which are monotone.
[8] Multifit has been extended to the more general problem of maximin-share allocation of chores.
The goal is to give to each agent, a set of chores worth at most r times the maximum value in an optimal scheduling based on i's valuations.
A naive approach is to let each agent in turn use the MultiFit algorithm to calculate the threshold, and then use the algorithm where each agent uses his own threshold.
However, this approach fails due to the non-monotonicity of FFD.
Then, in the first round, the agent of type B takes the bundle 51, 24 (the other agents cannot take it since for them the values are 51,25 whose sum is more than 75).In the following rounds, the following bundles are filled for the type A agents: so the last two chores remain unallocated.
[5] Using more elaborate arguments, it is possible to guarantee to each agent the same ratio of MultiFit.