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

to full text (204 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • December 2008
size22 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.
Static URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000106
 
URN:NBNurn:nbn:de:101:1-201203214865
IDNumber of report :
  • TR_0806