First-fit-decreasing (FFD) is an algorithm for bin packing.
Its input is a list of items of different sizes.
Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity.
In short: FFD orders the items by descending size, and then calls first-fit bin packing.
An equivalent description of the FFD algorithm is as follows.
In the standard description, we loop over the items once, but keep many open bins.
The performance of FFD was analyzed in several steps.
denotes the number of bins used by FFD for input set S and bin-capacity C. The lower bound example given in by Dósa is the following: Consider the two bin configurations: If there are 4 copies of
An important special case of bin-packing is that which the item sizes form a divisible sequence (also called factored).
A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2.
In this case, FFD always finds the optimal packing.
is not a monotonic function of the sizes of items in S: it is possible that an item shrinks in size, but the number of bins increases.
However, the FFD algorithm has an "asymptotic monotonicity" property, defined as follows.
If the 17 becomes 16, then the resulting packing is: Modified first fit decreasing (MFFD)[9] improves on FFD for items larger than half a bin by classifying items by size into four size classes large, medium, small, and tiny, corresponding to items with size > 1/2 bin, > 1/3 bin, > 1/6 bin, and smaller items respectively.
Then it proceeds through five phases: This algorithm was first studied by Johnson and Garey[9] in 1985, where they proved that
This bound was improved in the year 1995 by Yue and Zhang[10] who proved that
Best-fit-decreasing (BFD) is very similar to FFD, except that after the list is sorted, it is processed by best-fit bin packing.
Its asymptotic approximation ratio is the same as FFD - 11/9.