Covering a Few Submodular Constraints and Applications

We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N rightarrow ℝ_+, r monotone submodular functions f1,f2,ldots,fr over N and requirements b1,b2,ldots,br the goal is to find a minimum cost subset S subseteq N such that fi(S) ≥ bi for 1 ≤ i ≤ r. When r=1 this is the well-known Submodular Set Cover problem. Previous work citechekuri2022covering considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each fi 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 Omega(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 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 α ≥ 1 outputs a set S such that fi(S) ≥ (1-1/eα -ε)bi for each i ∈ [r] and mathbbE[c(S)] ≤ (1+ε)α · sfOPT. Second, when the fi are weighted coverage functions from a deletion-closed set system we obtain a (1+ε) (fracee-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.