Improved algorithms for minimum-membership geometric set cover

DOI10.1007/978-3-031-52213-0_8MaRDI QIDQ6547827zbMATH OpenFDO

Authors Sathish Govindarajan, Siddhartha Sarkar

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-52213-0_8

zbMATH Keywords

approximation algorithmscomputational geometryminimum ply coveringminimum-membership geometric set cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)

Recommendations

• Minimum-membership geometric set cover, revisited
• Minimum membership covering and hitting
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Minimum ply covering of points with unit squares
• Minimum membership covering and hitting

Cites work

• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A threshold of ln n for approximating set cover
• Approximation schemes for covering and packing problems in image processing and VLSI
• Computing and Combinatorics
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Geometric red-blue set cover for unit squares and related problems
• scientific article; zbMATH DE number 5764844 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved results on geometric hitting set problems
• Minimum ply covering of points with disks and squares
• Minimum ply covering of points with unit squares
• Minimum-membership geometric set cover, revisited
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Optimal packing and covering in the plane are NP-complete

Cited in

(4)

• Minimum ply covering of points with unit squares
• Minimum-membership geometric set cover, revisited
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Minimum membership geometric set cover in the continuous setting

This page was built for publication: Improved algorithms for minimum-membership geometric set cover

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