Optimality and approximability of the rectangle covering problem
Abstract of thesis entitled
OPTIMALITY AND APPROXIMABILITY OF THE RECTANGLE COVERING PROBLEM
submitted by CHUNG Yau-Lin
for the Degree of Master of Philosophy
at The University of Hong Kong
in August 2004
A board is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle is a subset of the board whose union is rectangular. The problem of finding a minimum sized collection of rectangles whose union is equal to a given board is called the minimum rectangle covering problem, which arises in a rich variety of applications (such as pattern recognition and integrated circuit manufacturing) and has attracted tremendous research efforts. The present thesis is devoted to the optimality and approximability of the minimum rectangle covering problem.
A board B is vertically convex if any two unit squares in the same column of B are joined by a vertical line in B. It can be shown that for any vertically convex board B, the minimum size of a rectangle cover is equal to the maximum number of unit squares of B, no two of which are contained in the same rectangle. In this thesis a proof of this min-max relation is given, and a by-product is a polynomial-time algorithm for the problem on vertically convex boards.
A board B is simply connected if it contains no holes. In this thesis it is proved that for any simply connected board B, the minimum size of a rectangle cover is at most two times the maximum number of unit squares of B, no two of which are contained in the same rectangle. The proof yields a 2-approximation algorithm for the minimum rectangle covering problem on simply connected boards.
Min-max relation plays important roles in operations research. In addition to their theoretical interests, they usually yield efficient algorithms for problems in consideration. So a natural question is to ask whether the min-max relation also holds for the rectangle covering problem on simply connected board. In this thesis a counterexample is given and a closely related min-max theorem with ?quare?in place of ?ectangle?is established.
A proof of the NP-completeness of the minimum rectangle covering problem is also given in this thesis, which implies that there is no polynomial-time algorithm for solving the general problem exactly unless NP = P.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:maxima and minima combinatorial optimization approximation theory np complete problems
Date of Publication:01/01/2004