A 4.31-approximation for the geometric unique coverage problem on unit disks
From MaRDI portal
Publication:2250456
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
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