A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
From MaRDI portal
Publication:902421
DOI10.1016/j.comgeo.2015.10.004zbMath1333.65021OpenAlexW2199339740MaRDI QIDQ902421
Yushi Uno, Yota Otachi, Yoshio Okamoto, Ryuhei Uehara, Takehiro Ito, Takeaki Uno, Shin-ichi Nakano
Publication date: 18 January 2016
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2015.10.004
Related Items (5)
Minimum ply covering of points with disks and squares ⋮ Unique Coverage with Rectangular Regions ⋮ Minimum membership covering and hitting ⋮ Maximum independent and disjoint coverage ⋮ Exact multi-covering problems with geometric sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Dispersion in disks
- Unit disk graphs
- Approximate algorithms for some generalized knapsack problems
- Systems of distant representatives
- A 4.31-approximation for the geometric unique coverage problem on unit disks
- Geometric red-blue set cover for unit squares and related 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
- PTAS for Weighted Set Cover on Unit Squares
- 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
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
This page was built for publication: A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
