On the geometric priority set cover problem

DOI10.1016/J.COMGEO.2023.101984MaRDI QIDQ6103173zbMATH OpenFDO

Authors Aritra Banik, Rajiv Raman, Saurabh Ray

Publication date 26 June 2023

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COMGEO.2023.101984

zbMATH Keywords

approximation algorithmsgeometric set coverlocal searchquasi-uniform sampling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Weighted geometric set multi-cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Faster approximation algorithms for geometric set cover
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces

Cites work

• -nets and simplex range queries
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Almost optimal set covers in finite VC-dimension
• Applications of random sampling in computational geometry. II
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation Schemes for Covering and Packing
• Constructing planar support for non-piercing regions
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Fast approximation algorithms for a nonconvex covering problem
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 3394958 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Maintaining the union of unit discs under insertions with near-optimal overhead
• On column-restricted and priority covering integer programs
• On Geometric Set Cover for Orthants
• On the discrete unit disk cover problem
• On the geometric set multicover problem
• On the hardness of approximating minimum vertex cover
• On the set multicover problem in geometric settings
• Optimal packing and covering in the plane are NP-complete
• Packing and covering with non-piercing regions
• Pseudo-Line Arrangements: Duality, Algorithms, and Applications
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Tight lower bounds for the size of epsilon-nets
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover problems revisited
• Weighted geometric set cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling

Cited in

(1)

• scientific article; zbMATH DE number 1947045 (Why is no real title available?)

This page was built for publication: On the geometric priority set cover problem

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