Hitting sets when the shallow cell complexity is small

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

David B. Shmoys, Sander Aarts

Publication date: 19 July 2024

zbMATH Keywords

computational geometryapproximation algorithmsset coverhitting setshallow cell complexitywireless coverage

Mathematics Subject Classification ID

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

Cites Work

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

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)