Almost optimal set covers in finite VC-dimension
From MaRDI portal
Publication:1906049
DOI10.1007/BF02570718zbMath0841.68122WikidataQ55883000 ScholiaQ55883000MaRDI QIDQ1906049
Michael T. Goodrich, Hervé Brönnimann
Publication date: 6 February 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131414
Related Items
Tighter estimates for \(\epsilon\)-nets for disks ⋮ Packing and covering with balls on Busemann surfaces ⋮ The maximum exposure problem ⋮ Guarding monotone art galleries with sliding cameras in linear time ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Geometric Hitting Sets for Disks: Theory and Practice ⋮ Universal Guard Problems ⋮ Guarding galleries and terrains ⋮ Exact learning from an honest teacher that answers membership queries ⋮ On dependent randomized rounding algorithms ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Hypergraph representation via axis-aligned point-subspace cover ⋮ Polygon guarding with orientation ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ On the geometric set multicover problem ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Approximately dominating representatives ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ The matroid intersection cover problem ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Improved results on geometric hitting set problems ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ The robust minimal controllability problem ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ Computing cup products in \(\mathbb{Z}_2\)-cohomology of 3D polyhedral complexes ⋮ Capacitated covering problems in geometric spaces ⋮ A Distributed Algorithm to Approximate Node-Weighted Minimum α-Connected (θ,k)-Coverage in Dense Sensor Networks ⋮ The class cover problem with boxes ⋮ Optimal partition trees ⋮ A scheme for computing minimum covers within simple regions ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ On the approximability of covering points by lines and related problems ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Unnamed Item ⋮ Constrained hitting set problem with intervals ⋮ A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ On the establishment of distinct identities in overlay networks ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Covering Polygons with Rectangles ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Greedy domination on biclique-free graphs ⋮ \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Unit disk cover problem in 2D ⋮ Cup Products on Polyhedral Approximations of 3D Digital Images ⋮ Geometric hitting set for segments of few orientations ⋮ On separating points by lines ⋮ Discrete unit square cover problem ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Approximation algorithms for the unit disk cover problem in 2D and 3D ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Packing and covering with non-piercing regions ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ On guarding the vertices of rectilinear domains ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Covering a line segment with variable radius discs ⋮ Limits of local search: quality and efficiency ⋮ The within-strip discrete unit disk cover problem ⋮ Hausdorff approximation of 3D convex polytopes ⋮ Exact and approximation algorithms for geometric and capacitated set cover problems ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets ⋮ Tight lower bounds for the size of epsilon-nets ⋮ COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ A clustering-based approach to kinetic closest pair ⋮ The set covering problem revisited: an empirical study of the value of dual information ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Bounding Embeddings of VC Classes into Maximum Classes ⋮ Hitting sets online and unique-MAX coloring ⋮ On the Discrete Unit Disk Cover Problem ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ On Capacitated Set Cover Problems ⋮ Unnamed Item ⋮ Hitting sets when the VC-dimension is small ⋮ On interval and circular-arc covering problems ⋮ Fast stabbing of boxes in high dimensions ⋮ Experiments with unit disk cover algorithms for covering massive pointsets ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ Linear time approximation of 3D convex polytopes ⋮ Decision Trees for Geometric Models ⋮ Constant round distributed domination on graph classes with bounded expansion ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Minimum entangling power is close to its maximum ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ ON THE DISCRETE UNIT DISK COVER PROBLEM ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Covering a set of points with a minimum number of equal disks via simulated annealing ⋮ A hybrid heuristic for the rectilinear picture compression problem ⋮ On the geometric priority set cover problem ⋮ Improved bounds for metric capacitated covering problems ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Monochromatic partitioning of colored points by lines ⋮ Unnamed Item ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Unnamed Item ⋮ Covering Points by Unit Disks of Fixed Location ⋮ Cutting polygons into small pieces with chords: Laser-based localization ⋮ The Maximum Exposure Problem. ⋮ Helly-type theorems for approximate covering ⋮ Combinatorial optimization algorithms for radio network planning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing coverage kernels under restricted settings ⋮ Bregman Voronoi diagrams ⋮ Domination in Geometric Intersection Graphs ⋮ On Geometric Set Cover for Orthants ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Approximability of covering cells with line segments ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ On Partial Covering For Geometric Set Systems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Unnamed Item ⋮ On capacitated covering with unit balls
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range searching with efficient hierarchical cuttings
- A deterministic view of random sampling and its use in geometry
- Construction of \(\epsilon\)-nets
- On learning a union of half spaces
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- Almost tight bounds for \(\epsilon\)-nets
- Reporting points in halfspaces
- Efficient partition trees
- Cutting hyperplanes for divide-and-conquer
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- An optimal convex hull algorithm in any fixed dimension
- Discrepancy and approximations for bounded VC-dimension
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- Density and dimension
- On the density of families of sets
- Learnability and the Vapnik-Chervonenkis dimension
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Product Range Spaces, Sensitive Sampling, and Derandomization
- Decision Trees for Geometric Models
- Reducibility among Combinatorial Problems
- Algorithms for polytope covering and approximation
- On the hardness of approximating minimization problems
- Efficient probabilistically checkable proofs and applications to approximations
- Improved bounds on weak ε-nets for convex sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
