{"id":"arxiv/2609.19714","url":"https://arxiv.org/abs/2609.19714","tags":["cs.DS","cs.DM","math.CO","math.PR"],"score":0,"title":"Improved Algorithms for Beck--Fiala with Bounded Sets","domain":"cs.DS","source":"arxiv","authors":["Dylan J. Altschuler"],"reviews":0,"subject":"cs.DS","summary":"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^*$ 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^*n))$ discrepancy. Moreover, if $d\\ge\\ell_j(n)$ for a fixed integer $j\\ge1$, the algorithm gives $O_j(\\sqrt d)$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}