Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
DOI10.1145/2582112.2582152zbMATH Open1398.68656OpenAlexW1977333786MaRDI QIDQ4635551FDOQ4635551
Pankaj K. Agarwal, Jiangwei Pan
Publication date: 23 April 2018
Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2582112.2582152
Recommendations
- Near-linear algorithms for geometric hitting sets and set covers
- Near-linear approximation algorithms for geometric hitting sets
- Near-linear approximation algorithms for geometric hitting sets
- Practical and efficient algorithms for the geometric hitting set problem
- Approximation algorithms for a geometric set cover problem
- scientific article; zbMATH DE number 7760156
- An exact algorithm for a class of geometric set-cover problems
- Improved approximation algorithms for geometric set cover
- Improved approximation algorithms for geometric set cover
- Exact and approximation algorithms for geometric and capacitated set cover problems
Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cited In (22)
- On separating points by lines
- Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs
- Tighter estimates for \(\epsilon\)-nets for disks
- Computing coverage kernels under restricted settings
- \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity
- Improved approximation algorithms for geometric set cover
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- The maximum exposure problem
- Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model
- PTAS for minimum cost multicovering with disks
- Title not available (Why is that?)
- On Geometric Set Cover for Orthants
- Practical and efficient algorithms for the geometric hitting set problem
- Geometric Hitting Sets for Disks: Theory and Practice
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- The Maximum Exposure Problem.
- Experiments with unit disk cover algorithms for covering massive pointsets
- Improved algorithms for minimum-membership geometric set cover
- Limits of local search: quality and efficiency
This page was built for publication: Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635551)
