Improved results on geometric hitting set problems
From MaRDI portal
Publication:603882
Recommendations
- Practical and efficient algorithms for the geometric hitting set problem
- New results on a family of geometric hitting set problems in the plane
- Improved local search for geometric hitting set
- Near-linear approximation algorithms for geometric hitting sets
- Near-linear approximation algorithms for geometric hitting sets
- Improved approximation algorithms for geometric set cover
- Near-linear algorithms for geometric hitting sets and set covers
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Improved approximation algorithms for geometric set cover
- Geometric hitting sets for disks: theory and practice
Cites work
- scientific article; zbMATH DE number 3648730 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- A local search approximation algorithm for \(k\)-means clustering
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Covering Points by Unit Disks of Fixed Location
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast approximation algorithms for a nonconvex covering problem
- Hitting sets when the VC-dimension is small
- Improved approximation algorithms for geometric set cover
- Improved results on geometric hitting set problems
- Independent set of intersection graphs of convex objects in 2D
- Local search heuristic for k-median and facility location problems
- New existence proofs ε-nets
- Reducibility among combinatorial problems
- Weighted geometric set cover via quasi-uniform sampling
- \(\epsilon\)-nets and simplex range queries
Cited in
(92)- Capacitated covering problems in geometric spaces
- Discrete unit square cover problem
- Approximation algorithms for minimum ply covering of points with unit squares and unit disks
- Improved and generalized algorithms for burning a planar point set
- scientific article; zbMATH DE number 7376034 (Why is no real title available?)
- Generalized class cover problem with axis-parallel strips
- Improved algorithms for minimum-membership geometric set cover
- A constant-factor approximation algorithm for red-blue set cover with unit disks
- A constant-factor approximation algorithm for red-blue set cover with unit disks
- On the line-separable unit-disk coverage and related problems
- scientific article; zbMATH DE number 7561427 (Why is no real title available?)
- Approximating dominating set on intersection graphs of rectangles and L-frames
- scientific article; zbMATH DE number 7651148 (Why is no real title available?)
- scientific article; zbMATH DE number 7650099 (Why is no real title available?)
- Constant-factor approximation for TSP with disks
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Improved bounds for metric capacitated covering problems
- PTAS for minimum cost multicovering with disks
- Exactly hittable interval graphs
- Geometric hitting set for line-constrained disks
- On the geometric priority set cover problem
- Minimum membership covering and hitting
- Covering and packing of rectilinear subdivision
- Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
- Geometric stabbing via threshold rounding and factor revealing LPs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Optimality of geometric local search
- On the geometric red-blue set cover problem
- Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- On the discrete unit disk cover problem
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- scientific article; zbMATH DE number 7651162 (Why is no real title available?)
- Minimum ply covering of points with disks and squares
- On pseudo-disk hypergraphs
- Minimum dominating set problem for unit disks revisited
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- A tight analysis of geometric local search
- An exact algorithm for a class of geometric set-cover problems
- Approximation algorithms for polynomial-expansion and low-density graphs
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Constructing planar support for non-piercing regions
- Covering moving points with anchored disks
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Approximation algorithms for geometric conflict free covering problems
- Near-linear algorithms for geometric hitting sets and set covers
- Unit disk cover problem in 2D
- Improved results on geometric hitting set problems
- A primal-dual algorithm for the minimum power partial cover problem
- Following a curve with the discrete Fréchet distance
- PTAS for geometric hitting set problems via local search
- Clustering geometrically-modeled points in the aggregated uncertainty model
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Capacitated discrete unit disk cover
- Geometric hitting sets for disks: theory and practice
- Line segment disk cover
- Geometric red-blue set cover for unit squares and related problems
- On Geometric Set Cover for Orthants
- Geometric dominating-set and set-cover via local-search
- Improved local search for geometric hitting set
- Simple PTAS's for families of graphs excluding a minor
- Existence of planar support for geometric hypergraphs using elementary techniques
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Capacitated covering problems in geometric spaces
- Location, pricing and the problem of Apollonius
- Practical and efficient algorithms for the geometric hitting set problem
- On the discrete unit disk cover problem
- Planar Support for Non-piercing Regions and Applications
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- On partial covering for geometric set systems
- On interval and circular-arc covering problems
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Limits of local search: quality and efficiency
- Minimum power partial multi-cover on a line
- The within-strip discrete unit disk cover problem
- Hitting and Piercing Rectangles Induced by a Point Set
- Discriminating Codes in Geometric Setups
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Local search strikes again: PTAS for variants of geometric covering and packing
- Tighter estimates for \(\epsilon\)-nets for disks
- Packing and covering with balls on Busemann surfaces
- An algorithmic framework for solving geometric covering problems -- with applications
- On the approximability of covering points by lines and related problems
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Packing and covering with non-piercing regions
- Geometric Packing under Nonuniform Constraints
- scientific article; zbMATH DE number 7236415 (Why is no real title available?)
- On the geometric set multicover problem
- Discretely following a curve
This page was built for publication: Improved results on geometric hitting set problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q603882)
