Online Discrepancy Minimization via Persistent Self-Balancing Walks

Abstract: We study the online discrepancy minimization problem for vectors in

m a t h b b R^{d}

in the oblivious setting where an adversary is allowed fix the vectors

x_{1}, x_{2}, l d o t s, x_{n}

in arbitrary order ahead of time. We give an algorithm that maintains

O (s q r t l o g (n d / d e l t a))

discrepancy with probability

1 - d e l t a

, matching the lower bound given in [Bansal et al. 2020] up to an

O (s q r t l o g l o g n)

factor in the high-probability regime. We also provide results for the weighted and multi-color versions of the problem.

This page was built for publication: Online Discrepancy Minimization via Persistent Self-Balancing Walks