本文研究多子模约束覆盖问题，给定一个有限集合N、成本函数c和r个单调子模函数f_i及要求b_i，目标是在最小成本下找到子集S满足f_i(S) >= b_i。当r=1时为子模集合覆盖问题。文章提出随机双标准近似算法，对任何整数alpha >= 1输出集合S，满足f_i(S) >= (1-1/e^alpha-epsilon)b_i且期望成本至多为(1+epsilon)alpha*OPT。此外，当f_i为从删除闭集系统来的加权覆盖函数时，给出(1+epsilon)(e/(e-1))(1+beta)近似解，其中beta是基础集合覆盖问题的近似比。这些结果表明对于固定r可达到与r=1相近的近似效果。

📚 本文研究多子模约束覆盖问题，给定集合N、成本函数c及r个子模函数f_i和需求b_i，目标在最小成本下找到满足所有约束的子集S。

🔍 当r=1时问题简化为经典的子模集合覆盖问题，即寻找满足单一子模函数约束的最小成本子集。

📈 文章提出随机双标准近似算法，对任何整数alpha >= 1输出集合S，满足f_i(S) >= (1-1/e^alpha-epsilon)b_i且期望成本至多为(1+epsilon)alpha*OPT。

📊 当f_i为从删除闭集系统来的加权覆盖函数时，给出(1+epsilon)(e/(e-1))(1+beta)近似解，其中beta是基础集合覆盖问题的近似比。

💡 这些结果表明对于固定r可达到与r=1相近的近似效果，为多约束优化问题提供了新的近似算法框架。

arXiv:2507.09879v1 Announce Type: cross 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 $\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 \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 $\alpha \ge 1$ outputs a set $S$ such that $f_i(S) \ge$ $(1-1/e^\alpha -\epsilon)b_i$ for each $i \in [r]$ and $\mathbb{E}[c(S)] \le (1+\epsilon)\alpha \cdot \sf{OPT}$. Second, when the $f_i$ are weighted coverage functions from a deletion-closed set system we obtain a $(1+\epsilon)$ $(\frac{e}{e-1})$ $(1+\beta)$-approximation where $\beta$ 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.