Constructive Discrepancy Minimization by Walking on the Edges
From MaRDI portal
Publication:3449569
DOI10.1137/130929400zbMath1330.68343arXiv1203.5747OpenAlexW2080024126MaRDI QIDQ3449569
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
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