Constructive Discrepancy Minimization by Walking on the Edges

DOI10.1137/130929400zbMath1330.68343arXiv1203.5747OpenAlexW2080024126MaRDI QIDQ3449569

Raghu Meka, Shachar Lovett

Publication date: 4 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.5747

zbMATH Keywords

random walksBrownian motiondiscrepancy

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Random walks on graphs (05C81)

Related Items (26)

The set splittability problem ⋮ Constructive Discrepancy Minimization by Walking on the Edges ⋮ Random Walks in Polytopes and Negative Dependence ⋮ Discrepancy in modular arithmetic progressions ⋮ Approximation-Friendly Discrepancy Rounding ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ Probabilistic existence of regular combinatorial structures ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ The Phase Transition of Discrepancy in Random Hypergraphs ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Discrepancy of arithmetic progressions in grids ⋮ Discrepancy theory and related algorithms ⋮ Constructive Discrepancy Minimization for Convex Sets ⋮ Unnamed Item ⋮ A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture ⋮ Flat Littlewood polynomials exist ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ Unnamed Item ⋮ Two proofs for shallow packings ⋮ Better Bin Packing Approximations via Discrepancy Theory ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ Unnamed Item ⋮ Algorithmic Aspects of Combinatorial Discrepancy ⋮ Do flat skew-reciprocal Littlewood polynomials exist? ⋮ Hardness of Rainbow Coloring Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• ``Integer-making theorems
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• An \(L_p\) version of the Beck-Fiala conjecture
• Constructive Discrepancy Minimization by Walking on the Edges
• Six Standard Deviations Suffice
• EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES
• Geometric discrepancy. An illustrated guide

This page was built for publication: Constructive Discrepancy Minimization by Walking on the Edges