Treffer: 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)$.