American Mathematical Society (AMS) (link).
Publication Year: 2022; Volume 265
ISBNs: 978-1-4704-6156-0 (print); 978-1-4704-6873-6 (online)
DOI: https://doi.org/10.1090/surv/265
Download complete book PDF here.
Table of Contents
Preface
Chapter 1. A Probabilistic Averaging Technique
1. Level Sets
2. Concentration Bounds for Sums of Bernoulli Variables
Chapter 2. First Constructions of Epsilon-Nets
1. Deterministic
2. Probabilistic
3. Improved Probabilistic Analysis
Chapter 3. Refining Random Samples
1. Linear-sized Nets for Disks in the Plane
2. Partitioning Segments in the Plane
3. Application: Forbidden Subgraphs
Chapter 4. Complexity of Set Systems
1. VC-dimension
2. Shallow-cell Complexity
Chapter 5. Packings of Set Systems
1. Packing Half-Spaces in R^d
2. A Packing Theorem for Combinatorial Set Systems
3. Applications of the Packing Theorem
Chapter 6. Epsilon-Nets: Combinatorial Bounds
1. A First Bound using Ghost Sampling
2. Optimal Epsilon-Nets using Packings
Chapter 7. Epsilon-Nets: An Algorithm
1. Special Case: Linear-sized Nets
2. General Case
Chapter 8. Epsilon-Nets: Weighted Case
1. Special Case: Linear-sized Nets
2. General Case
3. Application: Rounding Linear Programs
Chapter 9. Epsilon-Nets: Convex Sets
1. Weak Epsilon-nets
2. Application: Polytope Approximation
Chapter 10. VC-dimension of k-Fold Unions: Basic Case
1. Abstract Set Systems
2. Axis-Aligned Rectangles in the Plane
Chapter 11. VC-dimension of k-Fold Unions: General Case
1. Products of Set Systems
2. Geometric Set Systems in R^d
3. Lower bounds on Epsilon-Nets
Chapter 12. Epsilon-Approximations: First Bounds
1. Proof using Induction
2. Proof using Discrepancy
Chapter 13. Epsilon-Approximations: Improved Bounds
1. Improved Analysis via Chaining
2. Near-Optimal Bounds via Partitioning
Chapter 14. Epsilon-Approximations: Relative Case
1. Relative and Sensitive Approximations
2. Improved Bounds for Relative Approximations
Chapter 15. Epsilon-Approximations: Functional Case
1. A Functional View of Approximations
2. Application: Sensitivity and Coresets for Clustering
Chapter 16. A Summary of Known Bounds
1. LIST: Complexity of Geometric Set Systems
2. LIST: Epsilon-Nets
3. LIST: Epsilon-Approximations
