Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

On approximating rectangle tiling and packing

Tools
- Tools
+ Tools

Khanna, Sanjeev, Muthukrishnan, S. and Paterson, Michael S. (1998) On approximating rectangle tiling and packing. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-339.pdf - Other - Requires a PDF viewer.

Download (360Kb) | Preview

Request Changes to record.

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 by 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 algorithms for these problems.

Item Type: Report
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Tiling (Mathematics)
Series Name: Department of Computer Science research report
Publisher: University of Warwick. Department of Computer Science
Official Date: 1998
Dates:
DateEvent
1998Completion
Number: Number 339
Number of Pages: 10
DOI: CS-RR-339
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Funder: European Strategic Programme of Research and Development in Information Technology (ESPRIT)
Grant number: 20244 (ESPRIT)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us