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

zum Volltext (204 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Dezember 2008
Seitenbereich22 S.

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.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000106
 
URN:NBNurn:nbn:de:101:1-201203214865
IDNummer des Berichts :
  • TR_0806