Hitting sets when the shallow cell complexity is small

DOI10.1007/978-3-031-49815-2_12MaRDI QIDQ6574945FDOQ6574945

Authors: Sander Aarts, David B. Shmoys 

Publication date: 19 July 2024

zbMATH Keywords

computational geometryapproximation algorithmsset coverhitting setshallow cell complexitywireless coverage

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• A Greedy Heuristic for the Set-Covering Problem
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Almost optimal set covers in finite VC-dimension
• Epsilon nets and union complexity
• Title not available (Why is that?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• A simple proof of the shallow packing lemma
• Small-size ε-nets for axis-parallel rectangles and boxes
• Title not available (Why is that?)
• A Randomized Algorithm for Closest-Point Queries
• A simple proof of optimal epsilon nets
• Title not available (Why is that?)
• Sampling in Combinatorial and Geometric Set Systems

This page was built for publication: Hitting sets when the shallow cell complexity is small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6574945)