Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10225740 | Information Processing Letters | 2019 | 7 Pages |
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
Raghunath Reddy Madireddy, Apurva Mudgal,