Search

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the minimum number of lines parallel to the x and y axes. We provide a 2-approximation algorithm, while the best known approximation ratio for this problem is O(logn). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which, given an mx × my array of nonnegative integers and positive integers v, h, asks to find a set of v vertical and h horizontal lines such that the maximum load of a subrectangle (i.e., the sum of the numbers in it) is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as it is known to be NP-hard to approximate within any factor less than 2. The results are then extended to the d-dimensional space for d ≥ 2, where a d-approximation algorithm for the stabbing problem and a dd-approximation algorithm for the partitioning problem are developed. [Copyright &y& Elsevier]