A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

DOI10.1137/1.9781611973402.101zbMATH Open1421.68075OpenAlexW2951116190MaRDI QIDQ5384063FDOQ5384063

Authors: Esther Ezra 

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.101

Recommendations

• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• On discrepancy bounds via dual shatter function
• Tight upper bounds for the discrepancy of half-spaces
• The determinant bound for discrepancy is almost tight
• Discrepancy and approximations for bounded VC-dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial complexity of geometric structures (52C45)

Cited In (4)

• Discrepancy and approximations for bounded VC-dimension
• A simple proof of the shallow packing lemma
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Title not available (Why is that?)

This page was built for publication: A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

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