1. Problembeschreibung und einfache Beobachtungen
2. Approximative Lösung des Online Bin-Packing-Problems
3. Approximative Lösung des Offline Bin-Packing-Problems
Problembeschreibung
Gegeben:
n Objekte der Größen
s1, ... , sn
mit 0 < si 1, für 1 i n.
Gesucht:
Die kleinstmögliche Anzahl von Kisten (Bins) der Größe 1, mit der alle
Objekte verpackt werden können.
Beispiel:
7 Objekte mit Größen 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8
Problembeschreibung
Online Bin-Packing:
Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die
es zuerst gepackt wird.
Offline Bin-Packing:
Zunächst wird die Anzahl n und alle n Objekte vorgegeben. Dann
beginnt die Verpackung.
Beobachtung
Bin-Packing ist beweisbar schwer.
(Offline Version ist NP-hart.
Entscheidungsproblem ist NP-vollständig.)
Kein Online Bin-Packing Verfahren kann stets
eine optimale Lösung liefern.
Online Verfahren
1/2 0 .... ..... 1 2 m m + 1 m + 2 2m Zeit 1 Satz 1
Es gibt Eingaben, die jeden Online Bin-Packing-Algorithmus zwingen,
wenigstens 4/3 OPT Bins zu verwenden, wobei OPT die minimal
mögliche Binzahl ist.
Beweis:
Annahme: Es gibt einen Online Bin-Packing-Algorithmus A, der stets weniger als 4/3 OPT Bins benötigt.
Online Verfahren
Zeitpunkt 1:
OPT = m/2 und #Bins(A) = b
Es gilt nach Annahme: b < 4/3 m/2 = 2/3 m
Sei b = b1 + b2 , wobei
b1 = #Bins mit einem Objekt
b2 = #Bins mit zwei Objekten
Es gilt: b1 + 2 b2 = m , d.h. b1 = m – 2b2
und damit b = b1 + b2 = m – b2 ()
Online Verfahren
Zeitpunkt 2:
OPT = m
#Bins(A) b + m – b1 = m + b2
Annahme: m + b2 #Bins( A ) < 4/3 m
b2 < m/3
mit (): b = m – b2 > 2/3 m
Online Verfahren
Next-Fit (NF), First-Fit (FF), Best-Fit (BF)
Next-Fit:
Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn
es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es
dort.
Satz 2
(a) Für alle Inputfolgen I gilt:
NF(I) 2 OPT(I).
(b) Es gibt Inputfolgen I mit:
NF(I) 2 OPT(I) – 2.
Next Fit
0 1 B1 B2 B2k-1 B2k Beweis: (a)
Betrachte zwei Kisten B2k-1, B2k, 2k NF( I ).
Next Fit
0 1 B1 B2 Bn/4 Bn/4 + 1 0.5 0.5 0.5 0.5 0.5 0.5 2/n 2/n 2/n .......... ..... Beweis: (b)
Betrachte Inputfolge I mit Länge n
(n 0 ( mod 4)):
0.5, 2/n, 0.5, 2/n, 0.5, ... , 0.5, 2/n
Optimale Packung:
Next Fit
0 1 B1 B2 Bn/2 .......... 2/n 0.5 0.5 2/n 2/n 0.5 Next Fit liefert:
NF ( I ) =
OPT ( I ) =
First Fit
First Fit:
Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst,
wenn es eine solche Kiste gibt, sonst in eine neue Kiste.
Beobachtung:
Es kann niemals mehr als eine Kiste geben, die
höchstens halb voll ist.
FF( I ) 2 OPT( I )
First Fit
Satz 3
(a) Für alle Inputfolgen I gilt:
FF( I ) 17/10 OPT( I )
(b) Es gibt Inputfolgen I mit:
FF( I ) 17/10 (OPT( I ) – 1)
(b´) Es gibt Inputfolgen I mit:
FF( I ) = 10/6 OPT( I )
First Fit
Beweis (b`): Inputfolge der Länge 3 6m
First Fit
First-Fit liefert:
First Fit
.........
Best Fit
Best Fit:
Verpacke das nächste Objekt in diejenige Kiste, in die es am besten
passt (d.h. den geringsten Platz ungenutzt lässt).
Verhalten von BF ähnlich zu FF
Laufzeit für Inputfolgen der Länge n
NF O(n)
FF O(n2) O(n log n)
BF O(n2) O(n log n)
Offline Verfahren
n und s1, ..., sn sind gegeben, bevor die Verpackung beginnt
Optimale Packung kann durch erschöpfende Suche
bestimmt werden.
Idee für offline Approximationsalgorithmus:
Sortiere die Objekte zunächst nach abnehmender
Größe und verpacke größere Objekte zuerst!
First Fit Decreasing (FFD) bzw. FFNI
Best Fit Decreasing (BFD)
First Fit Decreasing
Lemma 1
Sei I eine Folge von n Objekten mit Größen
s1 s2 ..... sn
und sei m = OPT(I).
Dann haben alle von FFD in den Bins
Bm+1,Bm+2, ... , BFFD(I)
verpackten Objekte eine Größe von jeweils höchstens 1/3.
Comments