Constructive Algorithms for Discrepancy Minimization

Understand

Given a set system (V,S), V={1,...,n} and S={S1,...,Sm}, the minimum discrepancy problem is to find a 2-coloring of V, such that each set is colored as evenly as possible.

• In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method.
• We also give a first approximation-like result for discrepancy.
• The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach $-1$ or $+1$.