Hitting Set for hypergraphs of low VC-dimension
From MaRDI portal
Publication:4606292
DOI10.4230/LIPIcs.ESA.2016.23zbMath1397.68092arXiv1512.00481OpenAlexW2962684085MaRDI QIDQ4606292
Karl Bringmann, Shay Moran, N. S. Narayanaswamy, László Kozma
Publication date: 2 March 2018
Full work available at URL: https://arxiv.org/abs/1512.00481
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Fractional covers of hypergraphs with bounded multi-intersection ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Finding and counting permutations via CSPs ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
This page was built for publication: Hitting Set for hypergraphs of low VC-dimension
