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

09/02/2022

∙

by   Monika Csikos, et al.

∙

0

∙

share

We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system (X,𝒮), the discrepancy of a two-coloring χ:X→{-1,1} is defined as max_S ∈𝒮|χ(S)|, where χ(S)=∑_x ∈ Sχ(x). We propose a randomized algorithm which, for any d>0 and (X,𝒮) with dual shatter function π^*(k)=O(k^d), returns a coloring with expected discrepancy O(√(|X|^1-1/dlog|𝒮|)) (this bound is tight) in time Õ(|𝒮|·|X|^1/d+|X|^2+1/d), improving upon the previous-best time of O(|𝒮|·|X|^3) by at least a factor of |X|^2-1/d when |𝒮|≥|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 ε-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 O(|X|^1-1/d), 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.