Discrepancy theory and related algorithms (Q6200209)
From MaRDI portal
scientific article; zbMATH DE number 7822590
Language | Label | Description | Also known as |
---|---|---|---|
English | Discrepancy theory and related algorithms |
scientific article; zbMATH DE number 7822590 |
Statements
Discrepancy theory and related algorithms (English)
0 references
22 March 2024
0 references
Summary: We survey some classical results and techniques in discrepancy theory, and the recent developments in making these techniques algorithmic. The previous methods were typically based on non-constructive approaches such as the pigeonhole principle, and counting arguments involving exponentially many objects and volume of convex bodies. The recent algorithmic methods are based on an interesting interplay of methods from discrete Brownian motion, convex geometry, optimization, and matrix analysis, and their study has led to interesting new connections and progress in both discrepancy and algorithm design. For the entire collection see [Zbl 07816361].
0 references
discrepancy
0 references
combinatorics
0 references
algorithms
0 references
random walks
0 references
0 references
0 references