Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

Abstract

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an algorithm that finds a coloring with discrepancy $O((t\log n\log s{)}^{1/2})$ where $s$ is the maximum cardinality of a set. This improves upon the previous constructive bound of $O(t^{1/2}\log n)$ based on algorithmic variants of the partial coloring method, and for small $s$ (e.g.$s=\text{poly}(t)$) comes close to the non-constructive $O((t\log n{)}^{1/2})$ bound due to Banaszczyk. Previously, no algorithmic results better than $O(t^{1/2}\log n)$ were known even for $s=O(t^2)$. Our method is quite robust and we give several refinements and extensions. For example, the coloring we obtain satisfies the stronger size-sensitive property that each set $S$ in the set system incurs an $O((t\log n\log |S|{)}^{1/2})$ discrepancy. Another variant can be used to essentially match Banaszczyk's bound for a wide class of instances even where $s$ is arbitrarily large. Finally, these results also extend directly to the more general Komlós setting.

References in corpus (2)

• The Komlos Conjecture Holds for Vector Colorings
• Constructive Discrepancy Minimization by Walking on The Edges

Cited by in corpus (2)

• An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
• Algorithms to Approximate Column-Sparse Packing Problems