English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of finding a low discrepancy coloring for sparse setsystems where each element lies in at most $t$ sets. We give an algorithm thatfinds a coloring with discrepancy $O((t \log n \log s)^{1/2})$ where $s$ is themaximum cardinality of a set. This improves upon the previous constructivebound of $O(t^{1/2} \log n)$ based on algorithmic variants of the partialcoloring method, and for small $s$ (e.g.$s=\textrm{poly}(t)$) comes close tothe 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 andextensions. For example, the coloring we obtain satisfies the strongersize-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 toessentially match Banaszczyk's bound for a wide class of instances even where$s$ is arbitrarily large. Finally, these results also extend directly to themore general Koml\'{o}s setting.

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems