Constructive algorithms for discrepancy minimization

Abstract

Given a set system (V, S), V = {1, ... , n} and S = {S1; ... , Sm}, the minimum discrepancy problem is to find a 2-coloring X : V → {- 1, +1}, such that each set is colored as evenly as possible, i.e. find X to minimize maxj∈[m]| Σi∈SjX(i)|. 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. Specifically we give efficient randomized algorithms to: 1) Construct an O(n1/2) discrepancy coloring for general sets systems when m = O(n), matching the celebrated result of Spencer [17] up to O(1) factors. More generally, for m ≥ n, we obtain a discrepancy of O(n1/2 log(2m/n)). 2) Construct a coloring with discrepancy O(t1/2 log n), if each element lies in at most t sets. This matches the (nonconstructive) result of Srinivasan [19]. 3) Construct a coloring with discrepancy O(λ log(nm)), where λ is the hereditary discrepancy of the set system. 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. At each step the random hops for various elements are correlated by a solution to a semidefinite program, where this program is determined by the current state and the entropy method. © 2010 IEEE.