Algorithmentheorie
7 – Bin Packing
Tobias Lauer
WS 06/07
Bin Packing
1. Problembeschreibung und einfache Beobachtungen
2. Approximative Lösung des Online Bin-Packing-Problems
3. Approximative Lösung des Offline Bin-Packing-Problems
WS 06/07
2
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
WS 06/07
3
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.
WS 06/07
4
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.
WS 06/07
5
Online Verfahren
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.
1
1/2
0
WS 06/07
.....
....
1
2
m
m+1 m+2
2m
Zeit
6
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 ()
WS 06/07
7
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
WS 06/07
8
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.
WS 06/07
9
Next Fit
Beweis: (a)
Betrachte zwei Kisten B2k-1, B2k,
2k  NF( I ).
1
0
B1 B2
WS 06/07
B2k-1
B2k
10
Next Fit
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:
1
0.5
0.5
0.5
2/n
..........
0.5
0.5
B1
B2
0.5
0
WS 06/07
Bn/4
2/n
2/n
Bn/4 + 1
11
Next Fit
Next Fit liefert:
1
..........
2/n
2/n
0.5
0.5
0.5
B1
B2
Bn/2
0
2/n
NF ( I ) =
OPT ( I ) =
WS 06/07
12
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 )
WS 06/07
13
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 )
WS 06/07
14
First Fit
Beweis (b`): Inputfolge der Länge 3  6m
1
/ 7

,

,1/
7

 , 1
/ 3


,

,1/
3

 , 1
/ 2

,

,1/
2


6m
WS 06/07
6m
6m
15
First Fit
First-Fit liefert:
1/ 7  
1/ 7  
1/ 7  
1/ 7  
1 / 7   1 / 7  
1/ 7  
1/ 7  
1/ 7  
1/ 7  
1/ 7  
Bm
B1



1/ 7  
m
WS 06/07
1/ 3  
1/ 3  
1/ 3  
1/ 3  

Bm1
Bm


4

6m / 2
16
First Fit
.........
1/ 2  
1/ 2  
B4 m1
B m

10

6m
WS 06/07
17
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)
BF O(n2)
WS 06/07
O(n log n)
O(n log n)
18
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)
WS 06/07
19
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.
WS 06/07
20
First Fit Decreasing
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.
WS 06/07
21
First Fit Decreasing
Beweis:
Annahme: Es gibt mehr als m – 1 Objekte
x1,....,xm in I, die FFD in extra Kisten verpackt.
W1
B1
WS 06/07
W2
Wm
B2
Bm
Bm+1
22
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 ) =
WS 06/07
23
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 ).
WS 06/07
24
First Fit Decreasing
Beweis (b): Inputfolge der Länge 3  6m + 12m
1
/ 2
,

,1 /
2

 ,1
/ 4
2,

,1 /
4 
2
6m
6m
1
/ 4
,

,1 /
4

 ,1
/ 4
2,

,1 /
4 
2
6m
12 m
Optimale Packung:
1/4 + 
1/4 + 
1/4 + 2
1/4 + 2
1/4 - 2
1/4 - 2
1/4 + 2
1/4 + 2
.........
............
1/2 + 
1/2 + 
1/4 - 2
1/4 - 2
1/4 - 2
1/4 - 2
B
B6 m B6m 1
B9 m
1 
 
WS 06/07
6m
3m
25
First Fit Decreasing
First Fit Decreasing liefert:
1/4 - 
1/4 + 
1/4 + 2
..........
1/2 + 
...................
1/4 - 
1/4 + 
1/4 - 
1/4 + 
1/4 - 
..........
B
B 1
B
1 
 6 m
 8m
6m
2m
3m
OPT(I) = 9m
FFD(I) = 11m
WS 06/07
26

Microsoft PowerPoint Presentation: 07_Bin_Packing