Deterministic discrepancy minimization

DOI10.1007/S00453-012-9728-1MaRDI QIDQ2017871zbMATH OpenOpenAlexFDO

Authors N. Bansal, Joel 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

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

Recommendations

• Deterministic discrepancy minimization
• Algorithmic aspects of combinatorial discrepancy
• Constructive discrepancy minimization by walking on the edges
• The determinant bound for discrepancy is almost tight
• Deterministic discrepancy minimization via the multiplicative weight update method

Cites work

• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 2119731 (Why is no real title available?)
• Algorithmic derandomization via complexity theory
• An \(L_p\) version of the Beck-Fiala conjecture
• Balancing games
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Discrepancy after adding a single set
• Discrepancy of set-systems and matrices
• Geometric discrepancy. An illustrated guide
• Linear and hereditary discrepancy
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• Sequences, discrepancies and applications
• Six Standard Deviations Suffice
• The determinant bound for discrepancy is almost tight
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(14)

• Approximating hereditary discrepancy via small width ellipsoids
• Discrepancy-based additive bounding procedures
• Tight hardness results for minimizing discrepancy
• Limited discrepancy search revisited
• Semidefinite optimization in discrepancy theory
• Deterministic discrepancy minimization
• Constructive discrepancy minimization by walking on the edges
• Algorithmic aspects of combinatorial discrepancy
• Practical algorithms for low-discrepancy 2-colorings
• On-line balancing of random inputs
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Hierarchical design of fast minimum disagreement algorithms
• Six Standard Deviations Suffice
• Deterministic discrepancy minimization via the multiplicative weight update method

This page was built for publication: Deterministic discrepancy minimization

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