Improved Algorithms for Beck--Fiala with Bounded Sets

Abstract

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in \{0,1{\}}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let ${\log }^{\ast }$ denote the iterated logarithm and ${\ell }_j$ denote the $j$-fold composition of log. Assume $s\le \exp (O(\sqrt{d}))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt{d}(1+{\log }^{\ast }n))$ discrepancy. Moreover, if $d\ge {\ell }_j(n)$ for a fixed integer $j\ge 1$, the algorithm gives $O_j(\sqrt{d})$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

arXiv comment11 pages, comments welcome