On approximating rectangle tiling and packing

Sanjeev Khanna, S. Muthukrishnan, Mike Paterson

    Research output: Contribution to conferencePaper

    Abstract

    Our study of tiling and packing with rectangles in two-dimensional 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×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 two-dimensional 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 and packing problems that we study have similar properties: while it is easy to solve them optimally in one dimension, the two-dimensional versions become NP-hard. We design efficient approximation algorithm for these problems.

    Original languageEnglish (US)
    Pages384-394
    Number of pages11
    StatePublished - 1998
    EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
    Duration: Jan 25 1998Jan 27 1998

    Other

    OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
    CitySan Francisco, CA, USA
    Period1/25/981/27/98

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'On approximating rectangle tiling and packing'. Together they form a unique fingerprint.

  • Cite this

    Khanna, S., Muthukrishnan, S., & Paterson, M. (1998). On approximating rectangle tiling and packing. 384-394. Paper presented at Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .