Weighted geometric set cover with rectangles of bounded integer side lengths

DOI10.1016/j.dam.2022.03.004OpenAlexW4220933811WikidataQ114191465 ScholiaQ114191465MaRDI QIDQ2133398

Raghunath Reddy Madireddy, Apurva Mudgal

Publication date: 29 April 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.03.004

zbMATH Keywords

geometric set coversweep-line methodaxis-parallel rectangles\textsf{NP}-hardness\textsf{PTAS}bounded integer side lengths

Mathematics Subject Classification ID

Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)

Cites Work

• Exact algorithms and APX-hardness results for geometric packing and covering problems
• The within-strip discrete unit disk cover problem
• Optimal packing and covering in the plane are NP-complete
• \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
• Geometric red-blue set cover for unit squares and related problems
• Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
• PTAS for Weighted Set Cover on Unit Squares
• Approximation schemes for covering and packing problems in image processing and VLSI
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Tight lower bounds for the size of epsilon-nets

This page was built for publication: Weighted geometric set cover with rectangles of bounded integer side lengths