Constant Approximation Algorithms for Rectangle Stabbing and Related Problems

摘要

In this paper we present constant approximation algorithms for two NP-hard rectangle stabbing problems, called the weighted rectangle stabbing (WRS) problem and the rectangle stabbing with rejecting cost (RSRC) problem. In the WRS problem a set of axis-aligned rectangles is given, with each rectangle associated with a positive weight, and a set of weighted horizontal and/or vertical stabbing lines is sought so that each rectangle is intersected by at least one stabbing line with a weight (called cost) no less than that of the rectangle and the total cost (or weight) of all stabbing lines is minimized. In the RSRC problem each rectangle is associated with an additional positive rejecting cost and is required to be either stabbed by a stabbing line or rejected by paying its rejecting cost. For the WRS problem, we present a polynomial time 2e-approximation algorithm, where e is the natural logarithmic base. Our algorithm is based on a number of interesting techniques such as rounding, randomization, and lower bounding. For the RSRC problem, we give a 3e-approximation algorithm by using a simple but powerful LP rounding technique to identify those to-be-rejected rectangles. Our techniques are quite general and can be easily applied to several related problems, such as the stochastic rectangle stabbing problem and polygon stabbing problem from fixed directions. Algorithms obtained by our techniques are relatively simple and can be easily implemented for practical purpose.