A 2-approximation for 2D bin packing

zum Volltext (213 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • März 2009
Seitenbereich20 S.

We study the two|-dimensional geometrical bin packing problem (2DBP): given a list of rectangles, provide a packing of all these into the smallest possible number of $1\times1$ bins without rotating the rectangles. We present a $2$|-approximate algorithm, which improves over the previous best known ratio of $3$, matches the best results for the rotational case and also matches the known lower bound of approximability. Our approach makes strong use of a recently-discovered PTAS for a related knapsack problem and a new algorithm that can pack instances into $\OPT+2$ bins for any constant $\OPT$.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000100
 
URN:NBNurn:nbn:de:101:1-201203145786
IDNummer des Berichts :
  • TR_0904