A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
type: Item
instance of: scholarly article
title: A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
zbMATH Open document ID: 1333.65021
author: Takehiro Ito
author: Yoshio Okamoto
author: Yota Otachi
author: Ryuhei Uehara
author: Takeaki Uno
author: Yushi Uno
author: Shin-Ichi Nakano
published in: Computational Geometry
publication date: 2016-01-18T00:00:00Z
review text: The authors present a polynomial-time approximation scheme for the unit-square coverage problem. More precisely, if a set of points and a set of axis-parallel unique squares in the plane are given, then the authors want to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. The problem is interesting and has been introduced by \textit{T. Erlebach} and \textit{E. J. van Leeuwen} [New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 1267--1276 (2008; Zbl 1192.68743)] in the geometric version of the unique coverage problem. The paper consists of six parts. New results are established and in conclusion, the paper is well written and structured.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6532289
zbMATH Keywords: polynomial-time approximation scheme
zbMATH Keywords: unique coverage problem
zbMATH Keywords: dynamic programming
zbMATH Keywords: shifting strategy
reviewed by: Laurian Ioan Piscoran
MaRDI profile type: Publication
full work available at URL: j.comgeo.2015.10.004
OpenAlex ID: W2199339740
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: On the efficiency of polynomial time approximation schemes
cites work: Geometric red-blue set cover for unit squares and related problems
cites work: Approximate algorithms for some generalized knapsack problems
cites work: Unit disk graphs
cites work: Combination Can Be Hard: Approximability of the Unique Coverage Problem
cites work: Dispersion in disks
cites work: Q3579437
cites work: PTAS for Weighted Set Cover on Unit Squares
cites work: Systems of distant representatives
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: A 4.31-approximation for the geometric unique coverage problem on unit disks
cites work: A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
cites work: Q4821303
cites work: The parameterized complexity of unique coverage and its variants
cites work: Q3221403
DOI: 10.1016/J.COMGEO.2015.10.004
description: scientific article; zbMATH DE number 6532289