Reverse-Fit : Ein approximativer Algorithmus für das Strip-Packing-Problem

In dieser Arbeit wird ein approximativer levelorientierter Algorithmus namens Reverse-Fit für das Strip-Packing-Problem vorgestellt und analysiert. Dieser Algorithmus basiert auf einer Arbeit von Ingo Schiermeyer. Bei diesem Problem handelt es sich darum eine Menge von Rechtecken in einen Streifen zu packen, so dass eine minimale Packungshöhe entsteht. Hierbei sind die Rechtecke achsenparallel angeordnet und dürfen nicht rotiert werden. Sei OPT die Höhe einer optimalen Packung für eine Instanz L und sei RF(L) die Höhe der Packung die Reverse-Fit erzeugt. Das Ergebnis der hier vorgestellten Analyse ist RF(L)<= 2 OPT.