Weighted geometric set cover with rectangles of bounded integer side lengths

DOI10.1016/J.DAM.2022.03.004MaRDI QIDQ2133398zbMATH OpenOpenAlexWikidataFDO

Authors 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

\textsf{NP}-hardness\textsf{PTAS}axis-parallel rectanglesbounded integer side lengthsgeometric set coversweep-line method

Mathematics Subject Classification ID

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

Recommendations

• Weighted geometric set cover problems revisited
• Weighted covering numbers of convex sets
• Weighted geometric set cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling
• scientific article; zbMATH DE number 2081015
• An exact algorithm for a class of geometric set-cover problems
• Exact multi-covering problems with geometric sets
• On rectangular covering problems
• A generalization of the weighted set covering problem

Cites work

• \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Geometric red-blue set cover for unit squares and related problems
• Optimal packing and covering in the plane are NP-complete
• PTAS for weighted set cover on unit squares
• The Rectilinear Steiner Tree Problem is NP-Complete
• The within-strip discrete unit disk cover problem
• Tight lower bounds for the size of epsilon-nets

Cited in

(2)

• Weighted geometric set multi-cover via quasi-uniform sampling
• Set cover, hitting set, and independent set problems for some restricted classes of geometric objects

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2133398)