Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

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

zbMATH Keywords

coveringapproximation algorithmswireless networksgeometric optimizationdiscrete piercing

Mathematics Subject Classification ID

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