DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.139

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting

Authors: Tatiana Rocha Avila, Lars Rohwedder, and Leo Wennmann

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Tatiana Rocha Avila, Lars Rohwedder, and Leo Wennmann. Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avila_et_al:LIPIcs.ESA.2026.139,
  author =	{Avila, Tatiana Rocha and Rohwedder, Lars and Wennmann, Leo},
  title =	{{Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.139},
  URN =		{urn:nbn:de:0030-drops-272757},
  doi =		{10.4230/LIPIcs.ESA.2026.139},
  annote =	{Keywords: Combinatorial Optimization, Discrepancy Theory}
}

Search Results

Documents authored by Avila, Tatiana Rocha

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting

Abstract

Cite as

Thanks for your feedback!

Could not send message