ON WEIGHTED RECTANGLE PACKING WITH LARGE RESOURCES

摘要

We study the problem of packing a set of n rectangles with weights into a dedicated rectangle so that the weight of the packed rectangles is maximized. We consider the case of large resources, that is, the side length of all rectangles is at most 1 and the side lengths of the dedicated rectangle differ by a factor of at least 1/ε~4, for a fixed positive ε > 0. We present an algorithm which finds a rectangle packing of weight at least (1 - ε) of the optimum in time polynomial in n. As an application we show a (2 + ε)-approximation algorithm for packing weighted rectangles into k rectangular bins of size (a, b).