Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
DOI10.1145/2582112.2582152zbMATH Open1398.68656OpenAlexW1977333786MaRDI QIDQ4635551FDOQ4635551
Authors: Jiangwei Pan, Pankaj K. Agarwal 
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
- Faster approximation algorithms for geometric set cover
- 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 (28)
- On separating points by lines
- 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
- Online and dynamic algorithms for geometric set cover and hitting set
- PTAS for minimum cost multicovering with disks
- Geometric hitting sets for disks: theory and practice
- Clustering geometrically-modeled points in the aggregated uncertainty model
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Faster approximation algorithms for geometric set cover
- Title not available (Why is that?)
- On Geometric Set Cover for Orthants
- Practical and efficient algorithms for the geometric hitting set problem
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- Near-linear algorithms for geometric hitting sets and set covers
- Finding small hitting sets in infinite range spaces of bounded VC-dimension
- Near-linear approximation algorithms for geometric hitting sets
- 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
- Near-linear approximation algorithms for geometric hitting sets
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)
