Lemma 2
Sei I eine Folge von n Objekten mit Größen
s1 s2 ..... sn
und sei m = OPT( I ).
Dann ist die Anzahl der Objekte, die FFD in die Kisten
Bm+1,Bm+2, ... , BFFD(I)
verpackt, höchstens m – 1.
First Fit Decreasing
W1 W2 Wm B1 B2 Bm Bm+1 Beweis:
Annahme: Es gibt mehr als m – 1 Objekte
x1,....,xm in I, die FFD in extra Kisten verpackt.
Anzahl der Bins von FFD
Lemma 2: FFD muss ≤ m-1 Objekte in Extra-Bins verpacken
Lemma 1: jedes dieser Objekte hat eine Größe ≤ 1/3
FFD( I ) =
First Fit Decreasing
Satz
Für alle Inputfolgen I gilt:
FFD( I ) (4 OPT( I ) + 1)/3.
Satz
a. Für alle Inputfolgen I gilt:
FFD( I ) 11/9 OPT( I ) + 4.
b. Es gibt Inputfolgen I mit:
FFD( I ) = 11/9 OPT( I ).
Comments