Deterministic discrepancy minimization

DOI10.1007/S00453-012-9728-1zbMATH Open1308.90125OpenAlexW2144053122MaRDI QIDQ2017871FDOQ2017871

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

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

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)

Cites Work

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

Cited In (14)

• Approximating hereditary discrepancy via small width ellipsoids
• Tight hardness results for minimizing discrepancy
• Discrepancy-based additive bounding procedures
• 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
• Six Standard Deviations Suffice
• Hierarchical design of fast minimum disagreement algorithms
• 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)