Deterministic discrepancy minimization

DOI10.1007/s00453-012-9728-1zbMath1308.90125OpenAlexW2144053122MaRDI QIDQ2017871

Nikhil Bansal, J. H. Spencer

Publication date: 23 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9728-1

zbMATH Keywords

algorithmsdiscrepancyderandomization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items

On‐line balancing of random inputs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequences, discrepancies and applications
• Discrepancy of set-systems and matrices
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• Balancing games
• An \(L_p\) version of the Beck-Fiala conjecture
• Discrepancy after adding a single set
• Linear and Hereditary Discrepancy
• Algorithmic derandomization via complexity theory
• Six Standard Deviations Suffice
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• The determinant bound for discrepancy is almost tight
• Geometric discrepancy. An illustrated guide