Near-linear time approximation schemes for geometric maximum coverage

DOI10.1016/J.TCS.2017.11.026MaRDI QIDQ1748995zbMATH OpenOpenAlexFDO

Authors Kai Jin, Jian Li, Haitao Wang, Bowei Zhang, N. Zhang

Publication date 15 May 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.01836

zbMATH Keywords

polynomial-time approximation schemegeometric set covermaximum coverage

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: We study approximation algorithms for the following geometric version of the maximum coverage problem: Let $mathcalP$ be a set of $n$ weighted points in the plane. Let $D$ represent a planar object, such as a rectangle, or a disk. We want to place $m$ copies of $D$ such that the sum of the weights of the points in $mathcalP$ covered by these copies is maximized. For any fixed $varepsilon>0$, we present efficient approximation schemes that can find a $(1-varepsilon)$-approximation to the optimal solution. In particular, for $m=1$ and for the special case where $D$ is a rectangle, our algorithm runs in time $O(nlog(frac1varepsilon))$, improving on the previous result. For $m>1$ and the rectangular case, our algorithm runs in $O(fracnvarepsilonlog(frac1varepsilon)+fracmvarepsilonlogm+m(frac1varepsilon{)}^{O(min(sqrtm,frac1varepsilon))})$ time. For a more general class of shapes (including disks, polygons with $O(1)$ edges), our algorithm runs in $O(n(frac1varepsilon{)}^{O(1)}+fracmepsilonlogm+m(frac1varepsilon{)}^{O(min(m,frac1varepsilo{n}^2))})$ time.

Recommendations

• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Covering Many or Few Points with Unit Disks
• Covering many or few points with unit disks

Cites work

• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1947380 (Why is no real title available?)
• A PTAS for the Weighted Unit Disk Cover Problem
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• A threshold of ln n for approximating set cover
• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Almost optimal set covers in finite VC-dimension
• An analysis of approximations for maximizing submodular set functions—I
• An efficient algorithm for determining the convex hull of a finite planar set
• Approximation of convex bodies by rectangles
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximations and optimal geometric divide-and-conquer
• Covering many or few points with unit disks
• Covering point sets with two disjoint disks or squares
• Exact and approximation algorithms for clustering
• Faster all-pairs shortest paths via circuit complexity
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Geometric approximation algorithms
• Hitting sets when the VC-dimension is small
• Improved approximation algorithms for geometric set cover
• Introduction to algorithms.
• Necklaces, Convolutions, and X + Y
• Note—On a Modified One-Center Model
• On Approximating the Depth and Related Problems
• On a circle placement problem
• On the Complexity of Some Common Geometric Location Problems
• Optimal placement of convex polygons to maximize point containment
• PTAS for geometric hitting set problems via local search
• Translating a convex polygon to contain a maximum number of points.
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(8)

• An algorithmic framework for solving geometric covering problems -- with applications
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• scientific article; zbMATH DE number 7376034 (Why is no real title available?)
• Energy-constrained geometric coverage problem
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Approximation algorithms for finding maximum containing circle and sphere

This page was built for publication: Near-linear time approximation schemes for geometric maximum coverage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748995)