An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing

Simple item page
dc.creatorHarren, Rolf
dc.creatorvan Stee, Rob
dc.date2009-03-13
dc.date.accessioned2026-07-07T12:52:18Z
dc.date.available2026-07-07T12:52:18Z
dc.descriptionWe 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 for this problem with an absolute worst-case ratio of 2, which is optimal provided P != NP.
dc.identifierhttps://arxiv.org/abs/0903.2265
dc.identifierhttp://arxiv.org/abs/0903.2265
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/223254
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleAn Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing
dc.typetext

Files

Collections

arXiv