连续贪心算法 | Codeboy's Blog

形式陈述

先固定目标、oracle与边界

给有限拟阵M=(E,𝓘)，由独立性oracle回答任一标号子集是否独立；给精确value oracle f:2ᴱ→ℝ，要求f归一化、单调、子模。因此f非负。目标为

OPT=\max_{I\in\mathcal I}f(I).

f必须也能查询不独立的集合，因为多线性扩张F的随机子集不一定可行。输入oracle满足公理是一项承诺；少量测试不能自动验证任意拟阵或集合函数。

先查询所有单元素，删除不独立的loop；它们不能出现在任何可行解中。以下E表示保留的元素，n=|E|，r为秩。单调性允许把最优独立集扩充到一组基，故存在大小r的最优基O。

r=0时返回空集。否则令

M_1=\max_{i\in E}f(\{i\}).

每个保留单点可行，故M₁≤OPT。若M₁=0，边际递减给f(S)≤∑ᵢ∈Sf({i})=0，所有可行解值零，返回任一基即可。不能在删loop之前用同一个最大单例界。

有限步算法是实际执行接口

选整数L≥1，步长δ=1/L，从x⁰=0开始。每轮t=0,…,L−1：

求梯度gᵗ=∇F(xᵗ)，或给每坐标误差至多ηM₁的估计ĝᵗ
在所有基中求最大化∑ᵢ∈Bĝᵗᵢ的Bₜ，平局按固定元素编号处理
更新xᵗ⁺¹=xᵗ+δ1_{Bₜ}，并保存这组基及权重δ

第二步使用最大权基贪心：按当前梯度权重排序并依次做独立性测试。这里精确优化的是本轮的线性方向，不是直接对原子模目标逐项贪心。

令𝓑为基族。过程始终有

x^t=\delta\sum_{s<t}1_{B_s},\quad 0\le x_i^t\le t\delta\le1.

它是基指标与零向量的凸组合，所以在独立集凸包内；最终

x^L\in\operatorname{conv}\{1_B:B\in\mathcal B\}, \qquad x^L=\frac1L\sum_{t=0}^{L-1}1_{B_t}. \tag{1}

式(1)已经是一份显式基分解，可以合并相同基的权重。这里没有另外假设一台免费把分数点分解成基的机器。

有限误差保证

若每轮所有坐标均满足|ĝᵗᵢ−gᵗᵢ|≤ηM₁，则

F(x^L)\ge \left[1-(1-1/L)^L-2r\eta-\frac{r(r-1)}{2L}\right]OPT. \tag{2}

若右侧系数为负，可用F≥0替代。精确梯度取η=0。由于(1−1/L)^L≤e⁻¹，步数足够多、估计足够准时得到接近1−1/e的保留比例；有限L不是连续极限，不能无条件删去后两项。

将式(1)交给交换舍入，得到真正的基B并有条件期望E[f(B)|xᴸ及其分解]≥F(xᴸ)。分数点的数值保证与某一次随机基的取值不是同一个承诺。

直觉

每轮只前进一小段，但方向是一整组可行元素

普通子模贪心选入一个元素后就不再更改。连续贪心把“这轮认为值得选的一整组基”只加入δ份，再重新计算重叠收益。某个元素先前很有吸引力，不意味着它在全部L轮都应占满概率。

拟阵约束限制每轮方向，而不是要求独立抽样得到的每份随机集合都可行。最后得到一组基的平均，再用保持可行性的交换机制变成整数输出。

十二步中第一步选择ac，此后选择bc，分数点自零增长并保存两种基的精确权重 — 增长方向、步长与基分解

连续形式把离散更新写成ẋ(t)=1_{B(t)}。梯度对最优方向给瞬时增长至少OPT−F(x(t))，于是理想过程满足F(x(1))≥(1−e⁻¹)OPT。[1, §2.3] 本页实际算法采用有限Euler步骤，下面直接给离散证明；不需要假定执行器能够精确积分这条微分方程。

例子与边界

覆盖目标与两组配额

沿用覆盖集合

a:\{0,1,2\},\quad b:\{0,3,4\},\quad c:\{0,1,2\},\quad d:\{5\},

并要求{a,b}、{c,d}各最多选一项。它是秩2的分区拟阵，不是只限制总数≤2：例如ab的大小虽为2，仍不可行。

普通逐项子模贪心第一步在价值3的a、b、c中按编号选a。此后c没有新增覆盖，d新增1，所以选ad，最终值4；bc可行且值5，是最优基。

取L=12，用精确梯度。第0轮x=0，梯度(3,3,3,1)，最大权基按平局规则为ac。更新后x=(1/12,0,1/12,0)。第1轮梯度变成

(11/4,\ 409/144,\ 11/4,\ 1),

于是方向改为bc。409/144=2+(11/12)²，比11/4大；b新增的独占区域此时开始胜过a的重复覆盖。

以后都选择bc。可直接核这一不变量：xₐ恒为1/12、x_d恒为0，x_c增长时a边际不超过11/4，b边际始终至少2；更精确地，令u=x_b，便有x_c=u+1/12，

g_b-g_a=\frac1{12}+\frac1{144}+3u-u^2>0,

而g_c=(11/12)(3−u)>1，所以c一直胜过d。最后

x^{12}=(1/12,11/12,1,0) =\tfrac1{12}1_{ac}+\tfrac{11}{12}1_{bc}.

c已经必选，覆盖区域0、1、2；b以11/12概率增加两个独占区域，因此F=3+2·11/12=29/6。交换舍入输出ac的概率1/12、bc的概率11/12，期望同为29/6；某次仍可能得到值3的ac。

式(2)对此12步示例只保证

F(x^{12})\ge \left[1-(11/12)^{12}-1/12\right]OPT.

系数约0.565，比实际29/30的相对值松得多。这个差别来自通用曲率上界，不能因为本例表现好便抹掉有限步误差。

价值很高但永远不可选的loop

再加元素ℓ，它覆盖一个价值10⁶的新区域，却规定任何含ℓ的集合都不独立。可行最优值仍是5。若直接设M₁=max全部单例值，就得到10⁶≤OPT这一错误不等式。

执行器先识别loop，只在剩余元素上采样、计算梯度和取最大单例。它保留原编号及ℓ的零坐标，正确得到M₁=3。删除loop不等于去掉“当前还没有被选中”的普通元素；后者可能在以后成为最佳方向。

单调、单拟阵与oracle精度的界限

若f非单调，把最优独立集扩成基可能降低值，梯度也可能为负；本页的基方向与gap证明不再适用。两个拟阵的共同独立族通常不满足单拟阵公理，不能直接调用同一最大权基工具。

附件的64样本版只展示采样和方向计算确实执行。它并未满足任意指定η、ρ的统一样本预算，因此报告不把某次采样结果当成带该参数的理论保证。精确版则枚举子集，并为指数工作付费。

推论与应用

从最优基得到梯度gap

固定当前x，逐个把最优基O中的坐标提高到1。单调性给F(x∨1_O)≥f(O)=OPT。由于梯度随其他坐标增大而不增，每个坐标的增长至多(1−xᵢ)gᵢ(x)。于是

OPT-F(x)\le\sum_{i\in O}(1-x_i)g_i(x) \le\sum_{i\in O}g_i(x). \tag{3}

后一不等式使用gᵢ≥0。若B最大化估计权重，每组基都有r个元素，因此

\sum_{i\in B}g_i \ge\sum_{i\in B}\widehat g_i-r\eta M_1 \ge\sum_{i\in O}\widehat g_i-r\eta M_1 \ge OPT-F(x)-2r\eta M_1. \tag{4}

没有假定O中的每个元素都能直接加入当前某个整数集合；这正是它与基数逐项贪心证明的接口区别。

给Euler余项一个确定上界

定义φ(s)=F(x+s1_B)，0≤s≤δ。全部混合二阶导数在[−M₁,0]，对角为零，所以φ″(s)≥−r(r−1)M₁。两次积分得

F(x+\delta1_B)-F(x) \ge\delta\sum_{i\in B}g_i-\frac{\delta^2r(r-1)M_1}{2}.

代入式(4)、M₁≤OPT，记C=2rη+r(r−1)/(2L)，有

F_{t+1}\ge(1-\delta)F_t+\delta(1-C)OPT.

从F₀=0迭代，精确得到F_L≥[1−(1−δ)ᴸ]·(1−C)OPT；把因子[1−(1−δ)ᴸ]≤1用于误差项，便得式(2)。即便C>1，代数递推仍成立，但提供的负下界没有额外信息。r=1时曲率余项为零，L=1的精确梯度已经选择最佳单例。

自适应梯度估计怎样共同可靠

对每个坐标，独立抽K份排除该坐标的随机子集，平均边际。条件于此前全部历史，当前x已经确定，新样本相互独立，边际在[0,M₁]中。Hoeffding不等式给

\Pr(|\widehat g_i-g_i|>\eta M_1\mid\text{此前历史}) \le2e^{-2K\eta^2}.

给η>0、0<ρ<1，取

K\ge\left\lceil\frac{\ln(2nL/\rho)}{2\eta^2}\right\rceil,

则对全部nL项先取条件概率的总体平均、再并集上界，所有估计同时合格的概率至少1−ρ。没有要求各轮估计误差事件彼此独立；要求的是每项新采样在给定过去之后仍独立且服从当前x。

若式(2)的非负系数为A，分数点以至少1−ρ概率达到A·OPT。交换舍入对每个输入分解都保证条件期望，失败事件上又有f≥0，因此无条件结论是

\mathbb E f(B)\ge(1-\rho)A\,OPT.

这不是“以同样高概率，每个舍入输出都达到A·OPT”。例如给0<ε<1，可选η=ε/(8r)、L≥2r²/ε、ρ≤ε/2，把两阶段总期望损失控制在ε内，得到至少(1−1/e−ε)OPT；这组数只是简单充分预算，并非最优查询复杂度。

时间、位数与实际分解

令N为删除loop前的底集大小，n仍为保留元素数。设一次value查询需T_f，一次独立性查询需T_ind，集合以标号集合保存。附件每次独立性查询传入不可变集合副本，包含O(r+1)复制/校验；每轮最大权基花O(n log(n+1)+n(r+T_ind+1))。预处理单点、求秩和M₁也收费。附件保留原标号，梯度/点轨迹向量仍长N，每轮另有O(N)初始化、校验及复制。

精确梯度的教学实现总算术工作为

O\!\left(1+T_f+(N+1)(T_{ind}+1)+L\,[N+n(n+T_f)2^n+n\log(n+1)+n(r+T_{ind}+1)]\right)

其中1+T_f计入入口的f(∅)=0检查，N+1计入空集独立性查询和N个单点检查。n=0在入口扫描后直接返回，不做L轮；若N=n=0，含Matroid初始化的工作为O(1+T_f+T_ind)，已有初始化对象时euler本身为O(1+T_f)。若N>0而全是loop，仍须支付N项扫描和长度N的输出费用。采样梯度把轮内梯度项n(n+T_f)2ⁿ改为nK(n+T_f+1)，梯度阶段有2nLK次value查询和至多n(n−1)LK次Bernoulli抽取；采样维数按实际保留元素计。保存每轮完整梯度/点轨迹占O(LN)个数值，基分解最多L项；去掉教学轨迹可以省去这部分存储。

坐标分母整除L。附件用Fraction，以上是精确算术次数，不是任意大整数的单位成本宣称。理想独立随机位实现分母q的有理Bernoulli，可用拒绝采样取得[0,q)均匀整数，期望O(log(q+1))位；有限精度或相关随机源需另证。交换舍入的交换、oracle调用及可选日志成本另由其接口核算。

综合练习保存每轮梯度与所选基、重建最终分解，并同时交实际值、有限步下界与采样预算，三者不能混为一个数字。

参考资料

Gruia Calinescu、Chandra Chekuri、Martin Pál、Jan Vondrák，Maximizing a Monotone Submodular Function Subject to a Matroid Constraint，SICOMP40(6)，2011，§2.3、§3.1，印刷pp.1747–1752：连续过程、方向oracle、离散化和梯度估计；Appendix A另有更精细分析。本文显式保留简化Euler实现的误差，不把原文精细常数无条件移入。
Chandra Chekuri、Jan Vondrák、Rico Zenklusen，Dependent Randomized Rounding for Matroid Polytopes and Applications，§3：把已保存的基凸组合交给交换舍入。本文的覆盖数值、12步轨迹和有限预算由随附精确执行器复算。

形式陈述 ​

先固定目标、oracle与边界 ​

有限步算法是实际执行接口 ​

有限误差保证 ​

每轮只前进一小段，但方向是一整组可行元素 ​

覆盖目标与两组配额 ​

价值很高但永远不可选的loop ​

单调、单拟阵与oracle精度的界限 ​

从最优基得到梯度gap ​

给Euler余项一个确定上界 ​

自适应梯度估计怎样共同可靠 ​

时间、位数与实际分解 ​

反向链接