On Approximating Rectangle Tiling and Packing

Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and motion estimation in video compression by block matching, among others. An example of the problems that we tackle is the following: given an n \Theta n array A of positive numbers, find a tiling using at most p rectangles (that is, no two rectangles must overlap, and each array element must fall within some rectangle) that minimizes the maximum weight of any rectangle; here the weight of a rectangle is the sum of the array elements that fall within it. If the array A were one-dimensional, this problem could be easily solved by dynamic programming. We prove that in the twodimensional case it is NP-hard to approximate this problem to within a factor of 1:25. On the other hand, we provide a near-linear time algorithm that returns a solution at most 2:5 times the optimal. Other rectangle tiling..