Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Absolute Approximation Ratios for Packing Rectangles into Bins

MPG-Autoren
/persons/resource/persons44587

Harren,  Rolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Harren, R., & van Stee, R. (2012). Absolute Approximation Ratios for Packing Rectangles into Bins. Journal of Scheduling, 15(1), 63-75. doi:10.1007/s10951-009-0110-3.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-BCEA-7
Zusammenfassung
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P != NP. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung, Gary & Johnson [1982] and whose running time is slightly better than the running time of Zhang's previously known 3-approximation algorithm [2005].