Improved results on geometric hitting set problems
From MaRDI portal
Publication:603882
DOI10.1007/S00454-010-9285-9zbMATH Open1207.68420OpenAlexW2018541722MaRDI QIDQ603882FDOQ603882
Authors: Nabil H. Mustafa, Saurabh Ray 
Publication date: 8 November 2010
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-010-9285-9
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Almost optimal set covers in finite VC-dimension
- Weighted geometric set cover via quasi-uniform sampling
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- New existence proofs ε-nets
- Fast approximation algorithms for a nonconvex covering problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Covering Points by Unit Disks of Fixed Location
- Improved results on geometric hitting set problems
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Local search heuristic for k-median and facility location problems
- Independent set of intersection graphs of convex objects in 2D
- A local search approximation algorithm for \(k\)-means clustering
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved approximation algorithms for geometric set cover
- Title not available (Why is that?)
Cited In (96)
- Title not available (Why is that?)
- Line segment disk cover
- Discriminating Codes in Geometric Setups
- Capacitated discrete unit disk cover
- On partial covering for geometric set systems
- Tighter estimates for \(\epsilon\)-nets for disks
- Minimum ply covering of points with disks and squares
- On pseudo-disk hypergraphs
- Geometric Packing under Nonuniform Constraints
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Approximation algorithms for polynomial-expansion and low-density graphs
- Improved results on geometric hitting set problems
- Title not available (Why is that?)
- An algorithmic framework for solving geometric covering problems -- with applications
- A tight analysis of geometric local search
- Covering moving points with anchored disks
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Geometric hitting set for segments of few orientations
- Packing and covering with non-piercing regions
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
- Unit disk cover problem in 2D
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- On the discrete unit disk cover problem
- PTAS for geometric hitting set problems via local search
- Geometric hitting sets for disks: theory and practice
- Covering segments with unit squares
- Improved local search for geometric hitting set
- Simple PTAS's for families of graphs excluding a minor
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Location, pricing and the problem of Apollonius
- Clustering geometrically-modeled points in the aggregated uncertainty model
- Local search strikes again: PTAS for variants of geometric covering and packing
- Optimality of geometric local search
- Following a curve with the discrete Fréchet distance
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Approximability of covering cells with line segments
- Packing and covering with balls on Busemann surfaces
- On the geometric set multicover problem
- Minimum dominating set problem for unit disks revisited
- Constructing planar support for non-piercing regions
- On the discrete unit disk cover problem
- On the approximability of covering points by lines and related problems
- Discretely following a curve
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- On Geometric Set Cover for Orthants
- Geometric dominating-set and set-cover via local-search
- Existence of planar support for geometric hypergraphs using elementary techniques
- Practical and efficient algorithms for the geometric hitting set problem
- Online unit covering in Euclidean space
- Minimum power partial multi-cover on a line
- Title not available (Why is that?)
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Planar Support for Non-piercing Regions and Applications
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Near-linear algorithms for geometric hitting sets and set covers
- Capacitated covering problems in geometric spaces
- On interval and circular-arc covering problems
- A primal-dual algorithm for the minimum power partial cover problem
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Local search is a PTAS for feedback vertex set in minor-free graphs
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- An exact algorithm for a class of geometric set-cover problems
- Approximation algorithms for geometric conflict free covering problems
- Geometric red-blue set cover for unit squares and related problems
- Limits of local search: quality and efficiency
- The within-strip discrete unit disk cover problem
- Geometric hitting set for line-constrained disks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the geometric red-blue set cover problem
- On the geometric priority set cover problem
- Discrete unit square cover problem
- PTAS for minimum cost multicovering with disks
- Exactly hittable interval graphs
- On the line-separable unit-disk coverage and related problems
- Hitting and Piercing Rectangles Induced by a Point Set
- Constant-factor approximation for TSP with disks
- Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
- Minimum membership covering and hitting
- Covering and packing of rectilinear subdivision
- Capacitated covering problems in geometric spaces
- Improved and generalized algorithms for burning a planar point set
- Approximation algorithms for minimum ply covering of points with unit squares and unit disks
- 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
- Approximating dominating set on intersection graphs of rectangles and L-frames
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Improved bounds for metric capacitated covering problems
- Geometric stabbing via threshold rounding and factor revealing LPs
- Generalized class cover problem with axis-parallel strips
- Improved algorithms for minimum-membership geometric set cover
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)
