PreprintCC BY 4.0arXiv
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∈{0,1}m× n with at most d ones per column and at most s ones per row. Let log* denote the iterated logarithm and ℓj denote the j-fold composition of log. Assume s≤exp(O(√d)). We provide an efficient algorithm that, for arbitrary sparsity d, gives O(√d(1+log*n)) discrepancy. Moreover, if d≥ℓj(n) for a fixed integer j≥1, the algorithm gives Oj(√d) discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.
Related
- Online Beck--Fiala Down to Logarithmic Sparsity
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
- BiLipschitz and bounded displacement equivalence of Delone sets
- Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
- Bounded joins of biclosed sets
BibTeX
@misc{altschuler2026improved,
title = {{Improved Algorithms for Beck--Fiala with Bounded Sets}},
author = {Dylan J. Altschuler},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19714},
eprint = {2609.19714},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19714},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Algorithms for Beck--Fiala with Bounded Sets
AU - Dylan J. Altschuler
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19714
UR - https://arxiv.org/abs/2609.19714
AB - 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∈{0,1}^m× n with at most d ones per column and at most s ones per row. Let log^* denote the iterated logarithm and ℓ_j denote the j-fold composition of log. Assume s≤exp(O(√d)). We provide an efficient algorithm that, for arbitrary sparsity d, gives O(√d(1+log^*n)) discrepancy. Moreover, if d≥ℓ_j(n) for a fixed integer j≥1, the algorithm gives O_j(√d) discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.
ER -