Algorithmic aspects of combinatorial discrepancy

DOI10.1007/978-3-319-04696-9_6MaRDI QIDQ5264196zbMATH OpenOpenAlexFDO

Authors N. Bansal

Publication date 24 July 2015

Published in A Panorama of Discrepancy Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-04696-9_6

zbMATH Keywords

entropylow discrepancy coloringspartial hereditary discrepancy

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Irregularities of distribution, discrepancy (11K38) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Deterministic discrepancy minimization
• Constructive discrepancy minimization by walking on the edges
• Semidefinite optimization in discrepancy theory
• Deterministic discrepancy minimization via the multiplicative weight update method
• Deterministic discrepancy minimization

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1380581 (Why is no real title available?)
• scientific article; zbMATH DE number 6472647 (Why is no real title available?)
• Constructive discrepancy minimization by walking on the edges
• Deterministic discrepancy minimization
• Discrepancy after adding a single set
• Discrepancy of set-systems and matrices
• Elements of Information Theory
• Geometric discrepancy. An illustrated guide
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Indecomposable coverings with concave polygons
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• John's decompositions: Selecting a large part
• Linear and hereditary discrepancy
• On a combinatorial conjecture of Erdös
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• Semidefinite Programming
• Sequences, discrepancies and applications
• Six Standard Deviations Suffice
• The determinant bound for discrepancy is almost tight
• The entropy rounding method in approximation algorithms
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tight hardness results for minimizing discrepancy
• ``Integer-making theorems

Cited in

(10)

• Algorithmic discrepancy beyond partial coloring
• scientific article; zbMATH DE number 91009 (Why is no real title available?)
• Semidefinite optimization in discrepancy theory
• Discrepancy and sparsity
• Deterministic discrepancy minimization
• Constructive discrepancy minimization by walking on the edges
• Discrepancy without partial colorings
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Deterministic discrepancy minimization
• Deterministic discrepancy minimization via the multiplicative weight update method

This page was built for publication: Algorithmic aspects of combinatorial discrepancy

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