Article ID Journal Published Year Pages File Type
10225740 Information Processing Letters 2019 7 Pages PDF
Abstract
Further, we give a polynomial time approximation scheme (PTAS) for the weighted hitting set problem with axis-parallel rectangles when all rectangles have integer side lengths bounded by a constant C. Finally, we show that the problem is NP-hard for rectangles of size 1×2 and 2×1 even when every rectangle intersects a given unit height horizontal strip.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,