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

✍ Scribed by Daya Ram Gaur; Toshihide Ibaraki; Ramesh Krishnamurti

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 114 KB
• Volume: 43
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2002.1221

✦ Synopsis

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 x × m y 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 138