Near-linear algorithms for geometric hitting sets and set covers
From MaRDI portal
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
- Geometric hitting sets for disks: theory and practice
Cites work
- -nets and simplex range queries
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- A non-linear lower bound for planar epsilon-nets
- A sublinear-time randomized approximation algorithm for matrix games
- A threshold of ln n for approximating set cover
- Adaptive game playing using multiplicative weights
- Algorithms for polytope covering and approximation
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Computational geometry. Algorithms and applications.
- Decomposable searching problems I. Static-to-dynamic transformation
- Efficient partition trees
- Epsilon nets and union complexity
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Filtering Search: A New Approach to Query-Answering
- Geometric approximation algorithms
- Geometric Set Cover and Hitting Sets for Polytopes in R
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1241835 (Why is no real title available?)
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Improved approximation algorithms for geometric set cover
- Improved bounds for the union of locally fat objects in the plane
- Improved results on geometric hitting set problems
- Introduction to algorithms.
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Maximum independent set of rectangles
- Near-linear approximation algorithms for geometric hitting sets
- New existence proofs ε-nets
- New Lower Bounds for ϵ-nets
- On Approximating the Depth and Related Problems
- On the set multicover problem in geometric settings
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal halfspace range reporting in three dimensions
- Optimal packing and covering in the plane are NP-complete
- Quasi-optimal range searching in spaces of finite VC-dimension
- Reporting points in halfspaces
- Semialgebraic Range Reporting and Emptiness Searching with Applications
- Small-size -nets for axis-parallel rectangles and boxes
- Small-size relative ( p ,ε)-approximations for well-behaved range spaces
- The multiplicative weights update method: a meta-algorithm and applications
- Tight lower bounds for the size of epsilon-nets
- Tighter estimates for -nets for disks
Cited in
(32)- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- On the geometric set multicover problem
- An improved configuration checking-based algorithm for the unicost set covering problem
- Near-linear approximation algorithms for geometric hitting sets
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- Geometric hitting sets for disks: theory and practice
- Finding small hitting sets in infinite range spaces of bounded VC-dimension
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Geometric Set Cover and Hitting Sets for Polytopes in R
- Improved approximation algorithms for geometric set cover
- Near-linear approximation algorithms for geometric hitting sets
- Clustering geometrically-modeled points in the aggregated uncertainty model
- scientific article; zbMATH DE number 7662168 (Why is no real title available?)
- Improved results on geometric hitting set problems
- Faster approximation algorithms for geometric set cover
- Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- On the line-separable unit-disk coverage and related problems
- Online geometric covering and piercing
- Online and dynamic algorithms for geometric set cover and hitting set
- The online piercing set problem with recourse
- New lower bound and algorithm for online geometric hitting set problem
- Set cover, hitting set, and independent set problems for some restricted classes of geometric objects
- Algorithms for halfplane coverage and related problems
- On the line-separable unit-disk coverage and related problems
- On line-separable weighted unit-disk coverage and related problems
- Dynamic geometric set cover, revisited
- More dynamic data structures for geometric set cover with sublinear update time
- Online geometric hitting set using points in \(\mathbb{Z}^d\)
- On line-separable weighted unit-disk coverage and related problems
- Algorithms for halfplane coverage and related problems
- Improved approximation algorithms for geometric set cover
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 Q2291457)
