Polynomial time approximation schemes for minimum disk cover problems

DOI10.1007/S10878-009-9216-YMaRDI QIDQ613664zbMATHOpenAlexFDO

Authors Chen Liao, Shiyan Hu

Publication date 21 December 2010

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-009-9216-y

zbMATH Keywords

wireless networkminimum weight disk cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• An optimal algorithm for the minimum disc cover problem
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• Combining polynomial running time and fast convergence for the disk-covering method.
• Minimum-cost coverage of point sets by disks
• scientific article; zbMATH DE number 2009908
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Approximation algorithms for partial covering problems
• A polynomial time solvable instance of the feasible minimum cover problem
• On the discrete unit disk cover problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A better constant-factor approximation for weighted dominating set in unit disk graph
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• Almost optimal set covers in finite VC-dimension
• An optimal algorithm for the minimum disc cover problem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation schemes for wireless networks
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• The NP-completeness column: An ongoing guide
• Unit disk graphs

Cited in

(18)

• A PTAS for the disk cover problem of geometric objects
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
• scientific article; zbMATH DE number 3888915 (Why is no real title available?)
• Optimal cover of points by disks in a simple polygon
• A Scheme for Computing Minimum Covers within Simple Regions
• A scheme for computing minimum covers within simple regions
• Minimum-diameter covering problems
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Multiobjective Disk Cover Admits a PTAS
• Approximation algorithms for the class cover problem
• Minimum constellation covers: hardness, approximability and polynomial cases
• An improved approximation algorithm for the most points covering problem
• An optimal algorithm for the minimum disc cover problem
• Experiments with unit disk cover algorithms for covering massive pointsets
• A note on multicovering with disks
• Optimal cover of points by disks in a simple polygon
• A constant-factor approximation for multi-covering with disks

This page was built for publication: Polynomial time approximation schemes for minimum disk cover problems

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