Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
From MaRDI portal
Publication:2477196
DOI10.1016/j.comgeo.2007.01.001zbMath1152.65066OpenAlexW1978245018MaRDI QIDQ2477196
Matthew J. Katz, Paz Carmi, Nissan Lev-Tov
Publication date: 13 March 2008
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.01.001
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30)
Related Items (5)
Minimum Dominating Set Problem for Unit Disks Revisited ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ Piercing translates and homothets of a convex body ⋮ Piercing all translates of a set of axis-parallel rectangles ⋮ Piercing all translates of a set of axis-parallel rectangles
Cites Work
- Unnamed Item
- Unit disk graphs
- Almost optimal set covers in finite VC-dimension
- Dynamic data structures for fat objects and their applications
- Polynomial time approximation schemes for base station coverage with minimum total radii
- Approximation schemes for covering and packing problems in image processing and VLSI
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Improved approximation algorithms for geometric set cover
- Approximation and Online Algorithms
- The NP-completeness column: An ongoing guide
This page was built for publication: Polynomial-time approximation schemes for piercing and covering with applications in wireless networks