Near-linear time approximation schemes for geometric maximum coverage

DOI10.1016/j.tcs.2017.11.026zbMath1391.68111arXiv1702.01836OpenAlexW4243044215MaRDI QIDQ1748995

Haitao Wang, Kai Jin, Bowei Zhang, Jian Li, Ningye 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) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Cites Work

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