12.7

Let the First-Fit algorithm create bins B₁, B₂,…, B_F in that order and let OPT be the minimum (unknown) number of bins.

1. (Only one ‘‘small’’ bin) Assume two different bins, say B_i and B_j with i < j, each finish with load ≤ ½.
  • When the first object that starts B_j was examined, B_i still had free space ≥ ½.
  • If that object weighed ≤ ½ it would have fitted into B_i, contradicting First-Fit.
  • Therefore the object must weigh > ½, hence B_j ends up with load > ½ – a contradiction.
Hence at most one bin produced by First-Fit can have load ≤ ½; all others are > ½ full.

2. (Relating the totals) Let S be the total weight, [math]S=\sum_{k=1}^{n}w_k[/math].
  • Every bin except (possibly) one contains > ½ kg, so
    [math]S > (F-1)\times \tfrac12,[/math]  that is  [math]F-1 < 2S.[/math]
  • Because each optimal bin holds at most 1 kg, [math]\text{OPT} \ge S.[/math]

3. (Approximation bound) Combine the two inequalities:
    [math]F \le 2S \le 2\,\text{OPT}.[/math]

Therefore the First-Fit heuristic always uses no more than twice the minimum possible number of bins.

Back to Chapter 12