单调次模函数最大化

次模性让尚未选入的每个元素边际收益只会下降。最优集合对当前解的剩余优势可由至多 $k$ 个单元素边际上界，因此贪心每轮至少吃掉当前 gap 的 $1/k$；重复收缩便形成 $1-1/e$ 的指数衰减。

最大覆盖例子 ​

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

约束边界 ​

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

基数约束下每步加入边际增益最大的元素，是贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。；次模性保证剩余最优增益可由当前所有边际之和上界，从而递推出 1−1/e 保证。

Oracle 调用与 lazy greedy ​

朴素贪心每轮对所有未选元素调用 value oracle，共需 $O(nk)$ 次求值。次模性保证边际收益随 $S$ 增大只会下降，因此旧边际可以作为上界存入最大堆：弹出当前上界最大的元素后重新计算真实边际；若它仍不小于堆中其余上界，就安全地选择它，否则更新键值并放回。这个 lazy greedy 过程常显著减少实际 oracle 调用，但最坏情形仍可能反复重算，$1-1/e$ 保证来自“最终选中真实最大边际”这一不变量，而不是堆本身。

若只能找到 $(1-\eta )$ 近似最大边际，或 value oracle 带有加性、乘性误差，误差会逐轮进入 gap 递推，不能无条件沿用精确常数。在一般拟阵公理库拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。约束下，简单逐项贪心通常只有 $1/2$ 保证；达到 $1-1/e$ 需要 continuous greedy 与舍入等更强机制。拟阵因此是本问题的扩展边界，而不是基数约束定理的最低直接前置。