# Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical

arXiv: https://arxiv.org/abs/2209.01147 · HTML: https://mlsanity.com/paper/2209.01147/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 75 references that are in the map.
- First posted on arXiv 2 Sep 2022.

## Builds on (most cited first, 18 of 18)

- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [A Greedy Algorithm for Quantizing Neural Networks](https://mlsanity.com/paper/2010.15979/) (2020)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [On-Line Balancing of Random Inputs](https://mlsanity.com/paper/1903.06898/) (2019)
- [Online Vector Balancing and Geometric Discrepancy](https://mlsanity.com/paper/1912.03350/) (2019)
- [Constructive discrepancy minimization for convex sets](https://mlsanity.com/paper/1404.0339/) (2014)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [Online Discrepancy Minimization for Stochastic Arrivals](https://mlsanity.com/paper/2007.10622/) (2020)
- [A Logarithmic Additive Integrality Gap for Bin Packing](https://mlsanity.com/paper/1503.08796/) (2015)
- [Approximation-Friendly Discrepancy Rounding](https://mlsanity.com/paper/1512.02254/) (2015)
- [Online Discrepancy with Recourse for Vectors and Graphs](https://mlsanity.com/paper/2111.06308/) (2021)
- [Approximating Bin Packing within O(log OPT * log log OPT) bins](https://mlsanity.com/paper/1301.4010/) (2013)
- [An Algorithm for Koml'os Conjecture Matching Banaszczyk's bound](https://mlsanity.com/paper/1605.02882/) (2016)
- [Practical Low-Dimensional Halfspace Range Space Sampling](https://mlsanity.com/paper/1804.11307/) (2018)
- [Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method](https://mlsanity.com/paper/1611.08752/) (2016)
- [Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location](https://mlsanity.com/paper/1712.02913/) (2017)
- [Load Balancing: The Long Road from Theory to Practice](https://mlsanity.com/paper/2107.13638/) (2021)

## Abstract (arXiv)

We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system (X,mathcal S), the discrepancy of a two-coloring chi:X→-1,1 is defined as maxS ∈ mathcal S|chi(S)|, where chi(S)=sumlimitsx ∈ Schi(x). We propose a randomized algorithm which, for any d>0 and (X,mathcal S) with dual shatter function π^*(k)=O(kd), returns a coloring with expected discrepancy Oleft(√|X|1-1/dlog|mathcal S|right) (this bound is tight) in time tilde Oleft(|mathcal S|·|X|1/d+|X|2+1/dright), improving upon the previous-best time of Oleft(|mathcal S|·|X|3right) by at least a factor of |X|2-1/d when |mathcal S|≥|X|. This setup includes many geometric classes, families of bounded dual VC-dimension, and others. As an immediate consequence, we obtain an improved algorithm to construct varepsilon-approximations of sub-quadratic size. Our method uses primal-dual reweighing with an improved analysis of randomly updated weights and exploits the structural properties of the set system via matchings with low crossing number -- a fundamental structure in computational geometry. In particular, we get the same |X|2-1/d factor speed-up on the construction time of matchings with crossing number Oleft(|X|1-1/dright), which is the first improvement since the 1980s. The proposed algorithms are very simple, which makes it possible, for the first time, to compute colorings with near-optimal discrepancies and near-optimal sized approximations for abstract and geometric set systems in dimensions higher than 2.