Let be a set system with and . A ±1-coloring is a mapping . The *discrepancy* of a set system is defined as

,

where .

General bounds:

– Spencer ’85, Six standard deviations suffice, .

If every element appears in at most sets,

– Beck-Fiala ’81, “Integer-making” theorems, .

– Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, .

– Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, .

Constructive bounds:

– Bansal ’10, Constructive algorithms for discrepancy minimization.

Advertisements