A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares (Q902421)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares |
scientific article |
Statements
A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares (English)
0 references
18 January 2016
0 references
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.
0 references
polynomial-time approximation scheme
0 references
unique coverage problem
0 references
dynamic programming
0 references
shifting strategy
0 references
0 references
