On the geometric priority set cover problem
From MaRDI portal
Publication:6103173
DOI10.1016/j.comgeo.2023.101984zbMath1524.68399MaRDI QIDQ6103173
Aritra Banik, Saurabh Ray, Rajiv Raman
Publication date: 26 June 2023
Published in: Computational Geometry (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- On the hardness of approximating minimum vertex cover
- \(\epsilon\)-nets and simplex range queries
- Optimal packing and covering in the plane are NP-complete
- Applications of random sampling in computational geometry. II
- Almost optimal set covers in finite VC-dimension
- Packing and covering with non-piercing regions
- On the geometric set multicover problem
- Constructing planar support for non-piercing regions
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Weighted geometric set cover via quasi-uniform sampling
- On the set multicover problem in geometric settings
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- Weighted geometric set multi-cover via quasi-uniform sampling
- On the Discrete Unit Disk Cover Problem
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- On Column-Restricted and Priority Covering Integer Programs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Fast approximation algorithms for a nonconvex covering problem
- Approximation Schemes for Covering and Packing
- On Geometric Set Cover for Orthants
- Pseudo-Line Arrangements: Duality, Algorithms, and Applications
- A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
- Tight lower bounds for the size of epsilon-nets
This page was built for publication: On the geometric priority set cover problem