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

• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7561580 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A Randomized Algorithm for Closest-Point Queries
• A linear-time approximation algorithm for the weighted vertex cover problem
• A simple proof of optimal epsilon nets
• A simple proof of the shallow packing lemma
• Almost optimal set covers in finite VC-dimension
• Almost tight bounds for \(\epsilon\)-nets
• Epsilon nets and union complexity
• Hitting sets when the VC-dimension is small
• Sampling in combinatorial and geometric set systems
• Small-size ε-nets for axis-parallel rectangles and boxes
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• \(\epsilon\)-nets and simplex range queries

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)