Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem

Abstract

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(log n). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which, given an m × n array of non-negative integers, asks to find a set of vertical and horizontal lines such that the maximum load of a subrectangle (i.e., the sum of the numbers in it) is minimized. This problem arises when a mapping of an m × n array onto an h × v mesh of processors is required such that the largest load assigned to a processor is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as there is evidence that it is NP-hard to approximate within a factor of 2.