This paper considers the problem of handling multiple semimodular constraints. Given a finite set N, a cost function c: N → ℝ+, r monotonic semimodular functions f₁, f₂, …, fᵣ on N, and requirements b₁, b₂, …, bᵣ, the goal is to find a minimum cost subset S ⊆ N such that fᵢ(S) ≥ bᵢ (1 ≤ i ≤ r). For r = 1, this is the well-known semimodular set covering problem. In our previous work \cite{chekuri2022covering}, we developed a double-criteria approximation algorithm for large r and an approximation algorithm for the important special case where each fᵢ is a weighted covering function. These models are quite general and include many specific and interesting special cases. The approximation ratio for these problems is unavoidably at least Ω(log r) when r is part of the input. In this paper, inspired by recent applications, we consider the case where r is a fixed constant and obtain two main results. When dealing with multiple semimodular constraints, we obtain a randomized double-criteria approximation algorithm that outputs a set S such that fᵢ(S) ≥ (1-1/e^α -ε)bᵢ and E[c(S)] ≤ (1+ε)α · OPT for each i ∈ [r] for a given integer α ≥ 1. Second, when fᵢ is a weighted cover function of a deleted closed set system, we obtain a natural LP for the basis set cover instance, which yields an approximation of (1+ε)(e/(e-1))(1+β), where β is the approximation ratio. These results demonstrate that for fixed r, we can obtain an approximation that is nearly identical to that achievable when r = 1. We note several applications that readily follow from these general results and anticipate many more applications in the future.
