单调次模函数最大化

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

最大覆盖例子 ​

候选传感器各自覆盖一组区域，$f(S)$ 是被至少一个传感器覆盖的区域数。取 $A=\{1,2,3,4\}$、$B=\{1,2,5\}$、$C=\{3,4,6\}$，预算为 $2$。第一轮选覆盖四区的 $A$，第二轮 $B,C$ 都只新增一区，最终覆盖 $5$ 区；最优 $\{B,C\}$ 覆盖全部 $6$ 区。保证允许这样的损失：$k=2$ 的精确递推下界是 $3/4$，本例实际保留比例为 $5/6$。

约束边界 ​

非单调函数可能因加入元素而降值，证明第一步失效；非次模的互补收益也无法用单元素边际和上界 gap。

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

Oracle 调用与 lazy greedy ​

在 $1\le k<n$ 分支，缓存 $f(S)$ 后，朴素贪心共用 $O(nk)$ 次求值，另计 oracle 内部工作和集合表示成本；两个直接返回的边界分支无须执行这 $k$ 轮。次模性保证边际收益随 $S$ 增大只会下降，因此旧边际可以作为上界存入最大堆：弹出当前上界最大的元素后重新计算真实边际；若它仍不小于堆中其余上界，就安全地选择它，否则更新键值并放回。这个 lazy greedy 过程常显著减少实际 oracle 调用，但最坏情形仍可能反复重算，$1-1/e$ 保证来自“最终选中真实最大边际”这一不变量，而不是堆本身。

若只能找到 $(1-\eta )$ 近似最大边际，或 value oracle 带有加性、乘性误差，误差会逐轮进入 gap 递推，不能无条件沿用精确常数。在一般拟阵理路拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。约束下，简单逐项贪心通常只有 $1/2$ 保证；达到 $1-1/e$ 需要 continuous greedy 与舍入等更强机制。这类拟阵约束会改变交换结构，不能直接沿用“最优差由至多 $k$ 个任意可加入元素补齐”的基数论证。

连续贪心理路连续贪心算法Continuous greedy algorithm每轮用最大权拟阵基给多线性目标选择增长方向，以有限Euler步、显式梯度误差和可输出基分解实现接近1−1/e的近似。每轮以多线性梯度求最大权拟阵基，再只加入一小份基指标；有限步长与采样误差逐项进入近似界。保存的基凸组合随后由交换舍入理路拟阵交换舍入Swap rounding · Randomized swap rounding从显式基凸组合出发，以对称交换随机合并基，保持边缘概率与每次可行性，并用交换方向凸性证明子模目标期望不降。变成可行整数解，保证的是条件期望，而非每个随机分支都达到分数值。