非表示:
キーワード:
-
要旨:
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].
