Online balancing of sparse random vectors has a sharp complexity threshold
The threshold for online balancing of i.i.d. binary vectors
Data Structures and Algorithms
Summary
The paper studies how well an online algorithm can balance sequences of randomly arriving binary vectors with a certain number of ones. The authors found a precise threshold where the difficulty of the problem changes significantly depending on how many ones each vector has. If the vectors are very sparse, the challenge depends on a slow-growing function of the vector size; if they are less sparse, it depends on the square root of the number of ones. The study includes an efficient algorithm achieving the best possible balance.
What this means in practice
- •For algorithm designers: Prevent using inefficient heuristics in online balancing problems by knowing when sparsity influences hardness.
- •For data stream processors: Improve load balancing strategies by understanding when random sparse inputs affect discrepancy bounds.
A theory result. No direct application yet.
Authors
Dylan J. Altschuler, Konstantin Tikhomirov
Abstract
Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.