Constant Approximation Algorithms for Rectangle
Stabbing and Related Problems |
| |
Authors: | Guang Xu Jinhui Xu |
| |
Affiliation: | (1) Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|