2026-08-25T16:34:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27275 2026-08-25T13:18:20Z ddc:004 open_access

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting Avila, Tatiana Rocha Rohwedder, Lars Wennmann, Leo Combinatorial Optimization Discrepancy Theory Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem [Discrete Appl. Math '81], it remains widely open whether comparable non-additive bounds can be achieved. Towards a better understanding of non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs. More precisely, assuming each of the n items covers only t elements across all functions, we prove a constructive discrepancy bound that is polynomial in t, the number of colors k, and log n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatiana Rocha Avila and Lars Rohwedder and Leo Wennmann 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.139 urn:nbn:de:0030-drops-272757 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.139 eng https://creativecommons.org/licenses/by/4.0/legalcode