Maximizing the total profit of rectangles packed into a rectangle

We consider the following rectangle packing problem. Given a set of rectangles, each of which is associated with a profit, we are requested to pack a subset of the rectangles into a bigger rectangle so that the total profit of rectangles packed is maximized. The rectangles may not overlap. This problem is strongly NP-hard even for packing squares with identical profits. We first present a simple (3 + ϵ)-approximation algorithm. Then we consider a restricted version of the problem and show a (2 + ϵ)-approximation algorithm. This restricted problem includes the case where rotation by 90° is allowed (and is possible), and the case of packing squares. We apply a similar technique to the general problem, and get an improved algorithm with a worst-case ratio of at most 5/2 + ϵ. Finally, we devise a (2 + ϵ) approximation algorithm for the general problem.