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 max j∈ [m] i∈S j X (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(n 1/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(n 1/2 log(2m/n)). 2) Construct a coloring with discrepancy O(t 1/2 log n), if each element lies in at most t sets. This matches the (nonconstructive) result of Srinivasan [19] . 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. Index Terms-Discrepancy Theory, Constructive Algorithms. Let (V, S) be a set-system, where V = {1, . . . , n} are the elements and S = {S 1 , . . . , S m } is a collection of subsets of V . Given a {−1, +1} coloring X of elements in V , let X (S j ) = i∈Sj X (i) denote the discrepancy of X for set S. The discrepancy of the collection S is defined as disc(S) = min X max j∈[m] |X (S j )|. Understanding the discrepancy of various set-systems has been a major area of research both in mathematics and computer science, and this study has revealed fascinating connections to various areas of mathematics. Discrepancy also has a range of applications to several topics in computer science such as probabilistic and approximation algorithms, computational geometry, numerical integration, derandomization, communication complexity, machine learning, optimization and so on. We shall not attempt to describe these connections and applications here, but refer the reader to [6], [9], [12] . What is the discrepancy of an arbitrary set system with n elements and m sets?
Bansal REF showed that a semidefinite relaxation can be used to design a pseudo-approximation algorithm for hereditary discrepancy.
Constructive Algorithms for Discrepancy Minimization
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
Mathematics Computer Science