Algorithmic aspects of combinatorial discrepancy

DOI10.1007/978-3-319-04696-9_6zbMATH Open1358.11082OpenAlexW93640833MaRDI QIDQ5264196FDOQ5264196

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

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

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)

Cites Work

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

Cited In (10)

• Algorithmic discrepancy beyond partial coloring
• Title not available (Why is that?)
• 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 via the multiplicative weight update method
• Deterministic discrepancy minimization

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)