Constructive Discrepancy Minimization by Walking on the Edges
Constructive Discrepancy Minimization by Walking on the Edges
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there always exists a coloring which achieves …