{"ID":2894635,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09879","arxiv_id":"2507.09879","title":"Covering a Few Submodular Constraints and Applications","abstract":"We consider the problem of covering multiple submodular constraints. Given a finite ground set $N$, a cost function $c: N \\rightarrow \\mathbb{R}_+$, $r$ monotone submodular functions $f_1,f_2,\\ldots,f_r$ over $N$ and requirements $b_1,b_2,\\ldots,b_r$ the goal is to find a minimum cost subset $S \\subseteq N$ such that $f_i(S) \\ge b_i$ for $1 \\le i \\le r$. When $r=1$ this is the well-known Submodular Set Cover problem. Previous work \\cite{chekuri2022covering} considered the setting when $r$ is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each $f_i$ is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least $Ω(\\log r)$ which is unavoidable when $r$ is part of the input. In this paper, motivated by some recent applications, we consider the problem when $r$ is a \\emph{fixed constant} and obtain two main results. For covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer $α\\ge 1$ outputs a set $S$ such that $f_i(S) \\ge$ $(1-1/e^α-ε)b_i$ for each $i \\in [r]$ and $\\mathbb{E}[c(S)] \\le (1+ε)α\\cdot \\sf{OPT}$. Second, when the $f_i$ are weighted coverage functions from a deletion-closed set system we obtain a $(1+ε)$ $(\\frac{e}{e-1})$ $(1+β)$-approximation where $β$ is the approximation ratio for the underlying set cover instances via the natural LP. These results show that one can obtain nearly as good an approximation for any fixed $r$ as what one would achieve for $r=1$. We mention some applications that follow easily from these general results and anticipate more in the future.","short_abstract":"We consider the problem of covering multiple submodular constraints. Given a finite ground set $N$, a cost function $c: N \\rightarrow \\mathbb{R}_+$, $r$ monotone submodular functions $f_1,f_2,\\ldots,f_r$ over $N$ and requirements $b_1,b_2,\\ldots,b_r$ the goal is to find a minimum cost subset $S \\subseteq N$ such that $...","url_abs":"https://arxiv.org/abs/2507.09879","url_pdf":"https://arxiv.org/pdf/2507.09879v2","authors":"[\"Tanvi Bajpai\",\"Chandra Chekuri\",\"Pooja Kulkarni\"]","published":"2025-07-14T03:32:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\",\"cs.GT\"]","methods":"[]","has_code":false}