Discrepancy Without Partial Colorings
- Nicholas J. A. Harvey ,
- Roy Schwartz ,
- Mohit Singh
In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2014) |
Spencer’s theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be “colored” by the values ±1 such that the sum of every set is O( √ n) in absolute value. All existing proofs of this result recursively construct “partial colorings”, which assign ±1 values to half of the ground set. We devise the first algorithm for Spencer’s theorem that directly computes a coloring, without recursively computing partial colorings.