Full textReport2009UrhG

How to Maximize the Total Area of Rectangles Packed into a Rectangle?

We study an interesting geometric optimization problem. We are given a set of rectangles and a rectangular target area called bin. The goal is to find a feasible packing of a subset of the given rectangles into the bin, i.e. an orthogonal packing without rotation and overlap. The objective is to maximize the total area of rectangles packed. This problem is strongly $\mathcal{NP}$-hard even for squares, therefore there is no fully polynomial time approximation scheme (FPTAS) for this problem, unless $\mathcal{P}=\mathcal{NP}$. The previously best result is a $\left(\nicefrac{1}{2}-\varepsilon\right)$-approximation by Jansen \& Zhang for our problem. We present a polynomial time approximation scheme (PTAS) for this problem, i.e. a family of algorithms which compute for any accuracy $\varepsilon>0$ in polynomial time a solution with ratio $\left(1-\varepsilon\right)$.

Logo BII

BII

Cite

Citation style:
Could not load citation form.

Rights

Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.