A 4.31-approximation for the geometric unique coverage problem on unit disks

DOI10.1016/J.TCS.2014.04.014MaRDI QIDQ2250456zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Publication date 7 July 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.04.014

zbMATH Keywords

approximation algorithmcomputational geometryunique coverage problemunit disk

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• A 4.31-approximation for the geometric unique coverage problem on unit disks
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• scientific article; zbMATH DE number 7378687
• scientific article; zbMATH DE number 2081015
• The Parameterized Complexity of the Unique Coverage Problem
• A PTAS for the disk cover problem of geometric objects

Cites work

• A 4.31-approximation for the geometric unique coverage problem on unit disks
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Approximate algorithms for some generalized knapsack problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• scientific article; zbMATH DE number 5764844 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• The parameterized complexity of unique coverage and its variants

Cited in

(9)

• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Unique coverage with rectangular regions
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• On nonlinear multi-covering problems
• Maximum independent and disjoint coverage
• Local search strikes again: PTAS for variants of geometric covering and packing
• Maximum coverage in the data stream model: parameterized and generalized
• Minimum ply covering of points with disks and squares
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

This page was built for publication: A 4.31-approximation for the geometric unique coverage problem on unit disks

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