Source-linked AI summary
Constructive Algorithms for Discrepancy Minimization
Nikhil Bansal
TL;DR
The paper addresses constructive discrepancy minimization, where random colorings can incur an O((n log m)^1/2) bound. It develops iterative fractional-coloring algorithms based on tiny updates and controlled discrepancy, achieving polynomial-time bounds close to non-constructive results.
Problem
Random colorings guarantee discrepancy O((n log m)^1/2), and this bound is tight in general, motivating better constructive algorithms.
Method
The algorithms iteratively update a fractional coloring by tiny increments, stopping each element when its color reaches −1 or +1 while controlling set discrepancies through adjustable parameters.
Results
Theorem 1.1 gives a randomized polynomial-time algorithm achieving discrepancy O(n^1/2) for n sets and O(n^1/2 log(2m/n)) for m ≥ n; related procedures give O(t^1/2 log n).
Takeaways & Limitations
The paper provides constructive algorithms whose discrepancy guarantees are similar to known existential bounds, including a fractional-coloring reduction that halves alive variables while controlling discrepancy increases.
Takeaways & Limitations
For general m ≥ n, the algorithm has worse dependence on m/n than the tight non-constructive O(n^1/2 log(2m/n)^1/2) bound.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops the first polynomial-time algorithms matching several existential discrepancy bounds, including Spencer’s general-set result, Srinivasan’s bounded-degree result, and a hereditary-discrepancy guarantee. Its approach uses iterative semidefinite programs to coordinate random walks, addressing longstanding algorithmic and approximation questions.
- 1.1 Discrepancy of General Set Systems: Random coloring gives O((n log m)^1/2) discrepancy, while Spencer proved that every system with m ≥ n admits O((n log(2m/n))^1/2) discrepancy non-constructively.The paper targets the gap between this existential guarantee and efficient algorithms.
- 1.1 Discrepancy of General Set Systems: Before this work, no efficient algorithm improved on random coloring, and the paper resolves whether polynomial-time algorithms can achieve discrepancy O(n^1/2) when m = n.The prior difficulty was associated with the non-constructive use of the Pigeonhole Principle in Spencer’s result.
- 1.1 Discrepancy of General Set Systems: A randomized polynomial-time algorithm constructs discrepancy O(n^1/2) for n sets with probability at least 1/log n, and more generally O(n^1/2 log(2m/n)) with probability at least 1/log m.The general guarantee applies when m ≥ n.
- 1.1 Discrepancy of General Set Systems: For general m ≥ n, the constructive bound has worse dependence on m/n than the tight non-constructive O(n^1/2 log(2m/n)^1/2) bound.This is an explicit scope limitation of the general-set result.
- 1.2 Bounded Degree Sets: The Beck-Fiala Setting: For set systems of degree at most t, the paper gives a randomized polynomial-time construction with discrepancy O(t^1/2 log n), matching Srinivasan’s non-constructive bound.The success probability is at least 1/n.
- 1.3 Pseudo-Approximation and Hereditary Discrepancy: For hereditary discrepancy at most λ, the paper constructs a coloring with discrepancy O(λ log(mn)) in randomized polynomial time, answering a question of Matousek.The proof also relates hereditary discrepancy to hereditary vector discrepancy up to a logarithmic factor.
- 3 Our Approach: The algorithms iteratively solve semidefinite programs whose solutions define correlated random walks with tiny increments, stopping each element when its color reaches −1 or +1.The programs are guided by parameters from the entropy method, while adaptive set parameters control discrepancy beyond expectation.
2 Preliminaries
The preliminaries define discrepancy through signed set sums, then present the Entropy Method partial-coloring lemma and its phase-based applications to earlier existential bounds.
- Entropy Method: The Entropy Method produces a partial coloring assigning −1 or +1 to at least n/2 variables while bounding every set’s discrepancy by its prescribed ∆S.
- Entropy Method: The lemma follows from exponentially many colorings whose pairwise discrepancy differences are bounded, yielding a partial coloring from two colorings differing on Ω(n) coordinates.
- Spencer’s Result: Spencer’s phase construction repeatedly applies the lemma while the number of uncolored elements halves, using ∆S = c(ni log(2m/ni))^1/2.
- Srinivasan’s Result: Srinivasan’s phase analysis bounds the number of sets by uncolored-element ranges and enables ∆S = ct^1/2, leading to a total O(t^1/2 log n) discrepancy.
3 Our Approach
The approach turns partial-coloring guarantees into an iterative randomized process: SDP-guided Gaussian updates move element colors from zero toward ±1 while controlling set discrepancies.
- The algorithm starts with x0 = 0 and applies tiny updates γt until each element’s color reaches −1 or +1.Colors that reach a boundary become fixed.
- At each step, an SDP-derived update uses correlated Gaussian increments whose individual, aggregate, and set-sum variances satisfy prescribed bounds.
- Scaling the increments by γ makes element colors and set discrepancies martingales, while large progress fixes Ω(n) elements after O(1/γ^2) steps in expectation.
- The same procedure yields expected O(λ√log n) discrepancy under hereditary discrepancy λ, which becomes O(λ log(mn)) after tail bounds and a union bound.
- The initial expected O(n^1/2) discrepancy is insufficient for all sets, so the method adaptively lowers ∆S when sets become dangerous.
- Only a small fraction of sets become dangerous, preserving the entropy condition with suitable slack; multiple dangerous levels reduce discrepancy to O(n^1/2).
4 An pseudo-approximation for Discrepancy
The paper gives an SDP-based iterative algorithm and analyzes its termination, discrepancy concentration, and bounded-degree variant through Gaussian martingale arguments.
- The hereditary-discrepancy algorithm iteratively updates x0 = 0 until a final coloring xf ∈ {−1,+1}^n is obtained with discrepancy O(λ log(mn)).
- Variables reaching ±1 are fixed permanently, while the alive set A(t) tracks elements still receiving updates.
- Each iteration solves a feasible SDP, samples independent Gaussian coordinates, maps them through SDP vectors, and applies the resulting update.
- Rounding coordinates near the boundary changes total discrepancy by at most 1, while the probability of aborting over all iterations is at most 1/(mn)^4.
- After O(1/s^2) steps, the number of alive variables falls below half with probability at least 3/4, yielding a proper coloring with probability at least 1/n after O((log n)/s^2) steps.
- Constructive version of Srinivasan’s result: For bounded degree t, partial rather than complete colorings require 16/s^2-step epochs, and the resulting randomized algorithm achieves O(t^1/2 log n) discrepancy with probability at least 1/n.
5 Constructive version of Spencer’s result
The section develops a randomized polynomial-time construction achieving discrepancy O(n^1/2 log(2m/n)) for m ≥ n. Its iterative subroutine halves the number of alive variables while controlling set discrepancies through dangerous-set thresholds, entropy constraints, and probabilistic analysis.
- Subroutine guarantee: At most a/2 alive variables remain after one subroutine phase, while every set’s discrepancy increases by at most O(a^1/2 log(2m/a)) with probability at least 1/2.This theorem is the main iterative guarantee used to build the final coloring.
- Algorithm: The algorithm repeatedly solves an SDP to correlate fractional coloring increments, updating variables until enough reach ±1 or the phase limit is reached.The subroutine uses parameters s, q, d, and c, and rounds variables near the boundary to ±1.
- Dangerous sets: Sets are classified by danger levels, and the SDP assigns tighter discrepancy controls to sets whose accumulated discrepancy crosses successive thresholds.The feasibility proof uses entropy contributions and bounds on the number of dangerous sets at each level.
- Feasibility: The SDP remains feasible when sufficiently few sets are dangerous at each level, because the entropy method yields a feasible partial coloring on at least half the alive elements.Lemma 5.3 supplies the feasibility condition used in the phase analysis.
- Analysis: The analysis bounds the probability that many sets become dangerous and the probability that too many variables remain alive, yielding the subroutine’s success probability.Rounding contributes an additional O(a^1/2) discrepancy, and rare abort events are ignored or controlled probabilistically.