Algorithmic Aspects of Combinatorial Discrepancy

DOI10.1007/978-3-319-04696-9_6zbMath1358.11082MaRDI QIDQ5264196

Nikhil 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

entropy; low discrepancy colorings; partial hereditary discrepancy

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

11K38: Irregularities of distribution, discrepancy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Indecomposable coverings with concave polygons
• Sequences, discrepancies and applications
• Discrepancy of set-systems and matrices
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• ``Integer-making theorems
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Discrepancy after adding a single set
• Linear and Hereditary Discrepancy
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Bin Packing via Discrepancy of Permutations
• Deterministic Discrepancy Minimization
• Constructive Discrepancy Minimization by Walking on the Edges
• Six Standard Deviations Suffice
• Semidefinite Programming
• The determinant bound for discrepancy is almost tight
• Elements of Information Theory
• On a combinatorial conjecture of Erdös
• Geometric discrepancy. An illustrated guide
• John's decompositions: Selecting a large part