Full textReport2008UrhG

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.

Logo BII

BII

Cite

Citation style:
Could not load citation form.

Rights

Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.