Bin Packing Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
First Fit Decreasing
s1 s2 s3 ....................... si-1 si si+1 B1, ..... , Bm Bm+1 Beweis von Lemma 1:
Inputfolge I, absteigend sortiert
m = OPT(I)
i – kleinster Index, so dass si Bm+1
First Fit Decreasing
Beobachtung:
Gibt es eine Kiste mit drei Objekten in einer Verpackung
von s1,..., si , dann ist si 1/3
Annahme:
Alle Kisten in der FFD-Verpackung von s1,..., si enthalten
höchstens zwei Objekte.
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 von Lemma 2:
Annahme: Es gibt mehr als m – 1 Objekte
x1,....,xm in I, die FFD in extra Kisten verpackt.
First Fit Decreasing
Satz
Für alle Inputfolgen I gilt:
FFD( I ) (4 OPT( I ) + 1)/3.
First Fit Decreasing
Satz
Für alle Inputfolgen I gilt:
FFD( I ) (4 OPT( I ) + 1)/3.
Satz:
1. Für alle Inputfolgen I gilt:
FFD( I ) 11/9 OPT( I ) + 4.
2. Es gibt Inputfolgen I mit:
FFD( I ) = 11/9 OPT( I ).
Bin Packing Verfahren sind Beispiele für Greedy Algorithmen
Werden in vielen Lehrbüchern behandelt, z.B. in:
Mark Allen Weiss: Data Structures and Algorithm Analysis in C++,
The Benjamin/Cummings Publishing Comp., Redwood City,
1994
Vgl. dort Chapter 10.1.3
Comments