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

DOI10.1016/j.tcs.2014.04.014zbMath1357.68294OpenAlexW2050201659MaRDI QIDQ2250456

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

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 geometryunit diskunique coverage problem

Mathematics Subject Classification ID

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

Related Items

Minimum ply covering of points with disks and squares ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ On nonlinear multi-covering problems ⋮ Maximum independent and disjoint coverage ⋮ Local search strikes again: PTAS for variants of geometric covering and packing

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate algorithms for some generalized knapsack problems
• The parameterized complexity of unique coverage and its variants
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques