Improved algorithms for minimum-membership geometric set cover

DOI10.1007/978-3-031-52213-0_8MaRDI QIDQ6547827

Siddhartha Sarkar, Sathish Govindarajan

Publication date: 31 May 2024

zbMATH Keywords

computational geometryapproximation algorithmsminimum ply coveringminimum-membership geometric set cover

Mathematics Subject Classification ID

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

Cites Work

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

Related Items (1)

Approximation algorithms for minimum ply covering of points with unit squares and unit disks

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