Linear Time Approximation Schemes for Geometric Maximum Coverage

DOI10.1007/978-3-319-21398-9_44zbMath1391.68113arXiv1505.02591OpenAlexW1717598215MaRDI QIDQ3196415

Jian Li, Bowei Zhang, Ningye Zhang, Haitao Wang

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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
• 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

This page was built for publication: Linear Time Approximation Schemes for Geometric Maximum Coverage