Linear Time Approximation Schemes for Geometric Maximum Coverage
From MaRDI portal
Abstract: We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b rectangles such that the sum of the weights of the points in P covered by these rectangles is maximized.For any fixed > 0, we present efficient approximation schemes that can find (1-{epsilon})-approximation to the optimal solution.In particular, for m = 1, our algorithm runs in linear time O(n log( 1/{epsilon})), improving over the previous result. For m > 1, we present an algorithm that runs in O(n/{epsilon}log(1/{epsilon})+m(1/{epsilon})^(O(min(sqrt(m),1/{epsilon}))) time.
Recommendations
- Near-linear time approximation schemes for geometric maximum coverage
- scientific article; zbMATH DE number 7378687
- Approximation algorithms for a geometric set cover problem
- Faster approximation algorithms for geometric set cover
- Approximation algorithms for the Geometric Covering Salesman Problem
- Partial sublinear time approximation and inapproximation for maximum coverage
- Approximation algorithm for minimum partial multi-cover under a geometric setting
- Exact and approximation algorithms for geometric and capacitated set cover problems
- Exact and approximation algorithms for geometric and capacitated set cover problems
- scientific article; zbMATH DE number 7376034
Cites work
- 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 schemes for covering and packing problems in image processing and VLSI
- Covering many or few points with unit disks
- Covering point sets with two disjoint disks or squares
- 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
- Hitting sets when the VC-dimension is small
- scientific article; zbMATH DE number 1323125 (Why is no real title available?)
- scientific article; zbMATH DE number 1947380 (Why is no real title available?)
- Improved approximation algorithms for geometric set cover
- Introduction to algorithms.
- Necklaces, Convolutions, and X + Y
- Note—On a Modified One-Center Model
- On a circle placement problem
- On Approximating the Depth and Related Problems
- 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)- Near-linear time approximation schemes for geometric maximum coverage
- The maximum exposure problem
- Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons
- A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
- scientific article; zbMATH DE number 7376034 (Why is no real title available?)
- scientific article; zbMATH DE number 7378687 (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
This page was built for publication: 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 Q3196415)
