单调次模函数最大化

模型与算法 ​

给归一化 $f(\varnothing )=0$、非负、单调且次模公理库子模函数Submodular function定义在有限集合幂集上的边际收益递减函数。的 value-oracle 函数，目标是在 $|S|\le k$ 下最大化 $f(S)$。从 $S_0=\varnothing$ 开始，第 $i$ 步选择最大化

$$\mathrm{\Delta }(e\mid S_{i-1})=f(S_{i-1}\cup \{e\})-f(S_{i-1})$$

的元素 $e$。

递推证明 ​

令 $O$ 为最优大小至多 $k$ 的集合。由单调性和次模性，

$$OPT-f(S_{i-1})\le f(S_{i-1}\cup O)-f(S_{i-1})\le \sum _{e\in O\setminus S_{i-1}}\mathrm{\Delta }(e\mid S_{i-1}).$$

至多 $k$ 项中至少一项不小于 gap$/k$，贪心增益也至少如此。故

$$OPT-f(S_i)\le (1-1/k)(OPT-f(S_{i-1})),$$

迭代得 $f(S_k)\ge (1-(1-1/k{)}^k)OPT\ge (1-1/e)OPT$。

最大覆盖例子 ​

候选传感器各自覆盖一组区域，$f(S)$ 是被至少一个传感器覆盖的区域数。已覆盖区域不会再次贡献，边际收益随已选集合扩大而下降；贪心每轮选当前新增覆盖最多的传感器，正符合递推。

约束边界 ​

非单调函数可能因加入元素而降值，证明第一步失效；非次模的互补收益也无法用单元素边际和上界 gap。一般 matroid 约束下简单贪心通常只有 $1/2$，达到 $1-1/e$ 需 continuous greedy 等更强算法。oracle 调用 $O(nk)$ 也属于成本；若函数求值昂贵不能隐藏。

Lazy greedy ​

次模性使元素边际收益只会随 $S$ 增大而下降。可在最大堆保存旧边际作为上界：弹出元素后重新计算真实边际，若仍不小于堆中其他上界就选择，否则更新后放回。它常显著减少 oracle 调用，但最坏仍可能重算许多次，近似比来自选择真实最大边际的不变量。

若使用近似 oracle 或只找到 $(1-\eta )$ 近似最大边际，递推会累积额外误差；不能无条件保留精确 $1-1/e$ 常数。

Oracle 调用与惰性堆 ​

朴素贪心每轮对所有未选元素调用 value oracle，共 $O(nk)$ 次。次模性保证边际收益随集合增长只会下降，所以可把旧边际当上界放入最大堆；弹出元素后重新计算，若新值仍不小于其余上界才选择，否则以新值放回。

Lazy greedy 通常显著减少 oracle 次数，却不改变最坏 $1-1/e$ 证明，也不改善所有对抗实例的渐近上界。若函数只有近似 oracle，堆比较误差会影响选择质量，需要把每轮加性或乘性误差纳入递推。

在一般 matroid 约束下，简单逐项贪心只有 $1/2$ 级保证；要达到 $1-1/e$ 通常使用 continuous greedy 与舍入。不能把基数约束的递推原样推广到任意可行族。

参考资料

• George Nemhauser, Laurence Wolsey, Marshall Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions, Mathematical Programming, 1978.
• Gruia Calinescu et al., Maximizing a Monotone Submodular Function Subject to a Matroid Constraint, SICOMP, 2011.