Two-dimensional bin packing with one-dimensional resource augmentation

Two-dimensional bin packing with one-dimensional resource augmentation

0.00 Avg rating0 Votes
Article ID: iaor2008485
Country: Netherlands
Volume: 4
Issue: 2
Start Page Number: 143
End Page Number: 153
Publication Date: Jun 2007
Journal: Discrete Optimization
Authors: ,
Keywords: heuristics
Abstract:

The two-dimensional bin packing problem is a generalization of the classical bin packing problem and is defined as follows. Given a collection of rectangles specified by their width and height, pack these into a minimum number of square bins of unit size. Recently, the problem was proved to be APX-hard even in the asymptotic case, i.e. when the optimum solutions require a large number of bins. On the positive side, there exists a polynomial time algorithm that uses OPT bins whose sides have length (1+ε), where OPT denotes the number of unit sized bins used by the optimum solution. A natural question that remains is the approximability of the problem when we are allowed to relax the size of the unit bins in only one dimension. In this paper, we show that there exists an asymptotic polynomial time approximation scheme for packing rectangles into bins of size 1×(1+ε).

Reviews

Required fields are marked *. Your email address will not be published.