Improved results on geometric hitting set problems
From MaRDI portal
Publication:603882
DOI10.1007/s00454-010-9285-9zbMath1207.68420MaRDI QIDQ603882
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
52B55: Computational aspects related to convexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)
68W25: Approximation algorithms
Related Items
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Geometric Packing under Nonuniform Constraints, Constant-Factor Approximation for TSP with Disks, Discrete unit square cover problem, Unnamed Item, Unnamed Item, Hitting and Piercing Rectangles Induced by a Point Set, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames, Planar Support for Non-piercing Regions and Applications, On Geometric Set Cover for Orthants, On Partial Covering For Geometric Set Systems, Capacitated Covering Problems in Geometric Spaces, ON THE DISCRETE UNIT DISK COVER PROBLEM, Unnamed Item, Unnamed Item, Unnamed Item, Covering segments with unit squares, Minimum membership covering and hitting, A constant-factor approximation algorithm for red-blue set cover with unit disks, Capacitated discrete unit disk cover, Covering and packing of rectilinear subdivision, Line segment disk cover, A constant-factor approximation algorithm for red-blue set cover with unit disks, Online unit covering in Euclidean space, Local search strikes again: PTAS for variants of geometric covering and packing, Approximability of covering cells with line segments, Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., Improved and generalized algorithms for burning a planar point set, On the geometric priority set cover problem, Improved bounds for metric capacitated covering problems, Complexity and approximation for discriminating and identifying code problems in geometric setups, Exact algorithms and hardness results for geometric red-blue hitting set problem, Geometric dominating-set and set-cover via local-search, Geometric stabbing via threshold rounding and factor revealing LPs, Geometric hitting set for line-constrained disks, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), Discriminating Codes in Geometric Setups, Tighter estimates for \(\epsilon\)-nets for disks, 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, Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve, Exact algorithms and APX-hardness results for geometric packing and covering problems, Covering moving points with anchored disks, Unit disk cover problem in 2D, PTAS for minimum \(k\)-path vertex cover in ball graph, Limits of local search: quality and efficiency, The within-strip discrete unit disk cover problem, Improved results on geometric hitting set problems, On pseudo-disk hypergraphs, Minimum ply covering of points with disks and squares, On the approximability of covering points by lines and related problems, Approximability and hardness of geometric hitting set with axis-parallel rectangles, Location, pricing and the problem of Apollonius, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, Practical and efficient algorithms for the geometric hitting set problem, Geometric hitting set for segments of few orientations, Packing and covering with non-piercing regions, An exact algorithm for a class of geometric set-cover problems, A primal-dual algorithm for the minimum power partial cover problem, A tight analysis of geometric local search, On the geometric set multicover problem, Existence of planar support for geometric hypergraphs using elementary techniques, Capacitated covering problems in geometric spaces, Local search is a PTAS for feedback vertex set in minor-free graphs, Approximation algorithms for geometric conflict free covering problems, Constructing planar support for non-piercing regions, On the geometric red-blue set cover problem, Near-linear algorithms for geometric hitting sets and set covers, On interval and circular-arc covering problems, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Geometric red-blue set cover for unit squares and related problems, Simple PTAS's for families of graphs excluding a minor, Packing and covering with balls on Busemann surfaces, Minimum power partial multi-cover on a line, Discretely Following a Curve, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS, On the Discrete Unit Disk Cover Problem, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Geometric Hitting Sets for Disks: Theory and Practice, Minimum Dominating Set Problem for Unit Disks Revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Almost optimal set covers in finite VC-dimension
- Independent set of intersection graphs of convex objects in 2D
- 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
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A local search approximation algorithm for k-means clustering
- Reducibility among Combinatorial Problems
- Local search heuristic for k-median and facility location problems
- Approximation algorithms for maximum independent set of pseudo-disks
- Covering Points by Unit Disks of Fixed Location