Efficient improved algorithms solve Beck Fiala problem for bounded sets
Improved Algorithms for Beck--Fiala with Bounded Sets
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The Beck–Fiala problem involves splitting items into two groups so that the groups stay well balanced across many overlapping sets, especially when each item belongs to only a few sets. The authors present a better, faster algorithm to find such a balanced partition when each set includes only a limited number of items. Their method improves how closely balanced the groups can be, depending on the size and overlap of sets. They build upon previous algorithms to achieve these improvements effectively.
What this means in practice
- •For combinatorial optimization teams: Improve algorithms that require balanced selections from sets with few overlaps, enabling more efficient complex optimization procedures.
- •For algorithm engineers in scheduling: Design scheduling systems that handle tasks assigned to multiple limited-resource groups more evenly and efficiently.
A theory result. No direct application yet.
Authors
Dylan J. Altschuler
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^*$ 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)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.