A (5/3 + eps)- Approximation for Strip Packing

zum Volltext (490 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juli 2011
Seitenbereich32 S.

We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of 5/3+eps for any eps > 0. This result significantly narrows the gap between the best known upper bound and the lower bound of 3/2; previously, the best upper bound was 1.9396 due to Harren and van Stee.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000058
 
URN:NBNurn:nbn:de:101:1-201202285480
IDNummer des Berichts :
  • TR_1105