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 R_+, r monotone submodular functions f₁, f₂, , fᵣ over N and requirements b₁, b₂, , bᵣ the goal is to find a minimum cost subset S N such that fᵢ (S) bᵢ for 1 i r. When r=1 this is the well-known Submodular Set Cover problem. Previous work 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ᵢ 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 Ω (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 fᵢ (S) (1-1/e^α-ε) bᵢ for each i r and Ec (S) (1+ε) α OPT. Second, when the fᵢ are weighted coverage functions from a deletion-closed set system we obtain a (1+ε) (ee-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.