Hitting sets when the VC-dimension is small
From MaRDI portal
Publication:1041786
DOI10.1016/j.ipl.2005.03.010zbMath1184.68632OpenAlexW2058787216MaRDI QIDQ1041786
Guy Even, Dror Rawitz, Shimon (Moni) Shahar
Publication date: 4 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.03.010
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (44)
Tighter estimates for \(\epsilon\)-nets for disks ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Filtering algorithms for the NValue constraint ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ On the geometric set multicover problem ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Improved results on geometric hitting set problems ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ Geometric hitting set for line-constrained disks ⋮ The class cover problem with boxes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ 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 ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Greedy domination on biclique-free graphs ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ Geometric hitting set for segments of few orientations ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Packing and covering with non-piercing regions ⋮ Limits of local search: quality and efficiency ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Bregman Voronoi diagrams ⋮ The set covering problem revisited: an empirical study of the value of dual information ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Domination in Geometric Intersection Graphs ⋮ Hitting sets online and unique-MAX coloring ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Analysis of a first-fit algorithm for the capacitated unit covering problem ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ On interval and circular-arc covering problems ⋮ On Partial Covering For Geometric Set Systems ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ Unnamed Item ⋮ Sharp concentration of hitting size for random set systems ⋮ Constant round distributed domination on graph classes with bounded expansion ⋮ Computing Constrained Shortest-Paths at Scale
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- Almost optimal set covers in finite VC-dimension
- Learnability and the Vapnik-Chervonenkis dimension
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- A parallel approximation algorithm for positive linear programming
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Solving some discrepancy problems in NC
This page was built for publication: Hitting sets when the VC-dimension is small
