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 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$. At each time step the random hops for various elements are correlated using the solution to a semidefinite program, where this program is determined by the current state and the entropy method.

Fixed a previous erroneous claim about a logarithmic approximation for hereditary discrepancy. Other minor updates

Cited by in corpus (16)

• The Komlos Conjecture Holds for Vector Colorings
• Constructive Discrepancy Minimization by Walking on The Edges
• An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
• Discrepancy in random hypergraph models
• Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method
• A counterexample to Beck's conjecture on the discrepancy of three permutations
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
• Comparing Distributions and Shapes using the Kernel Distance
• Algorithmic Discrepancy Beyond Partial Coloring
• The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
• Integer Feasibility of Random Polytopes
• Randomised Rounding with Applications
• Improved Randomized Rounding using Random Walks
• epsilon-Samples of Kernels
• Variational Quantum Algorithms for Euclidean Discrepancy and Covariate-Balancing
• Balancing Polynomials in the Chebyshev Norm