Hitting sets when the VC-dimension is small
From MaRDI portal
Publication:1041786
DOI10.1016/j.ipl.2005.03.010zbMath1184.68632MaRDI 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
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
Constant-Factor Approximation for TSP with Disks, Tight lower bounds for the size of epsilon-nets, Distributed Dominating Set Approximations beyond Planar Graphs, Analysis of a first-fit algorithm for the capacitated unit covering problem, Computing Constrained Shortest-Paths at Scale, Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, On Partial Covering For Geometric Set Systems, Domination in Geometric Intersection Graphs, Unnamed Item, Bregman Voronoi diagrams, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., Complexity and approximation for discriminating and identifying code problems in geometric setups, Tighter estimates for \(\epsilon\)-nets for disks, Exact algorithms and APX-hardness results for geometric packing and covering problems, The class cover problem with boxes, Approximation algorithms for maximum independent set of pseudo-disks, Limits of local search: quality and efficiency, Improved results on geometric hitting set problems, A non-linear lower bound for planar epsilon-nets, Hitting sets online and unique-MAX coloring, Filtering algorithms for the NValue constraint, On the approximability of covering points by lines and related problems, Practical and efficient algorithms for the geometric hitting set problem, On the VC-dimension of unique round-trip shortest path systems, Greedy domination on biclique-free graphs, Geometric hitting set for segments of few orientations, Near-linear time approximation schemes for geometric maximum coverage, Packing and covering with non-piercing regions, Constant round distributed domination on graph classes with bounded expansion, On the geometric set multicover problem, The \(\varepsilon\)-\(t\)-net problem, Approximation algorithms for the connected sensor cover problem, On interval and circular-arc covering problems, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, Sharp concentration of hitting size for random set systems, Near-linear approximation algorithms for geometric hitting sets, The set covering problem revisited: an empirical study of the value of dual information, Exact learning from an honest teacher that answers membership queries, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, VC-Dimension and Shortest Path Algorithms, Linear Time Approximation Schemes for Geometric Maximum Coverage, A PTAS for the Weighted Unit Disk Cover Problem
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
