随机舍入 | Codeboy's Blog

形式陈述

随机舍入从一个离散优化问题的连续松弛解 $z$ 出发，规定条件于 $z$ 的随机离散输出规则 $R(z;\omega)$ ；概率来自算法使用的随机源，采用随机化算法的逐输入保证。松弛解可以是分数坐标，也可以是向量或矩阵。输出可直接满足原约束，也可先生成候选，再按明确规则修补；可行性和目标损失分别证明。

在线性规划松弛中，最基本的独立舍入给定 $x_j\in[0,1]$ ，抽取独立 $X_j\sim\operatorname{Bernoulli}(x_j)$ ；线性目标保持期望：

\mathbb E\sum_jc_jX_j=\sum_jc_jx_j.

这项期望线性性等式不保证整数约束成立。对不同问题，可以放大概率、重复抽样、按结构修补，或者构造带依赖的联合分布。下面用集合覆盖完成一条包含可行性与成本的完整证明。

输入、抽样与补选

给有限宇宙 $U$ ， $m=|U|\ge1$ ；集合 $S_1,\ldots,S_q$ 覆盖 $U$ ，成本 $c_j$ 非负且有限。输入一个可行分数解

0\le x_j\le1,\qquad \sum_{j:e\in S_j}x_j\ge1\quad(e\in U), \qquad L=\sum_{j=1}^q c_jx_j.

固定尺度 $\alpha\ge0$ 。算法如下：

对每个元素 $e$ ，预先选定一个包含它的最便宜集合 $j(e)$ ，并以集合编号消除平局，记 $c_e=c_{j(e)}$ 。
独立选择各集合，选择概率为 $p_j=\min\{1,\alpha x_j\}$ ，得到初选编号集 $R$ 。
求出初选后仍未覆盖的元素集 $U_0$ ，返回 $F=R\cup\{j(e):e\in U_0\}.$ 这里是集合并，同一个集合即使替多个元素补选，也只支付一次成本。

$U_0$ 按初选结果一次确定；第三步即便某个元素已被其他补选集合顺便覆盖，仍按既定集合并执行，这使规则和下例账本完全明确。每个样本结果都可行：原先覆盖的元素保留覆盖，其余元素都有自己的 $j(e)$ 。无需等一次幸运抽样才终止。若输入存在无集合可覆盖的元素，预处理便应报告实例不可行；给出的分数解违反约束时也不具有下面的保证。

期望成本定理与证明

对任意上述可行分数解与尺度，

\mathbb E[C(F)] \le(\alpha+m e^{-\alpha})L.

首先，截断概率可能降低成本，所以初选的正确关系是

\mathbb E[C(R)] =\sum_jc_jp_j\le\alpha L.

令 $Y_e$ 为元素 $e$ 初选后未覆盖的指示变量。若包含 $e$ 的某个集合以概率 $1$ 入选，则 $\Pr(Y_e=1)=0$ 。否则所有相关 $p_j=\alpha x_j<1$ ，独立性给出

\Pr(Y_e=1) =\prod_{j:e\in S_j}(1-\alpha x_j) \le\exp\left(-\alpha\sum_{j:e\in S_j}x_j\right) \le e^{-\alpha}.

这里使用 $1-t\le e^{-t}$ 和覆盖约束； $\alpha=0$ 时同样成立。其次，最便宜集合的成本满足

c_e \le c_e\sum_{j:e\in S_j}x_j \le\sum_{j:e\in S_j}c_jx_j \le L.

最后一步使用成本非负。逐个元素收费可能重复支付同一个补选集合，因此实际追加成本只满足上界

C(F)-C(R)\le\sum_{e\in U}c_eY_e.

取期望得到

\mathbb E[C(F)] \le\alpha L+\sum_e c_e\Pr(Y_e=1) \le\alpha L+m e^{-\alpha}L.

不同 $Y_e$ 通常相关，初选与补选成本也相关；线性期望不要求这些量独立。独立性只在未覆盖概率的乘积式中使用。

从分数成本到近似保证

取 $\alpha=\ln m$ ，便有

\mathbb E[C(F)]\le(1+\ln m)L.

它也是上述上界系数在 $\alpha\ge0$ 上的最小点，因为导数为 $1-me^{-\alpha}$ 。当 $m=1$ 时， $\alpha=0$ ，算法直接补选覆盖唯一元素的最便宜集合，边界不需排除。

若 $x$ 是最优 LP 解，则 $L=OPT_{\rm LP}\le OPT_{\rm int}$ ，故算法有 $(1+\ln m)$ 的期望近似比。若只给了任意可行分数解，本页保证仍相对于它的值 $L$ ；该值可能超过整数最优，不能自动换成同一近似比。近似求解 LP 时也须计入所得分数值相对最优值的误差。

直觉

初选阶段用分数解指出哪些集合值得买；尺度越大，买得越多，遗漏越少。补选阶段逐一照顾仍被遗漏的元素，其最坏费用可能很高，但每个元素进入这一步的概率已经下降。两项成本的平衡是 $\alpha L$ 与 $m e^{-\alpha}L$ ，对数尺度正是在平衡这两项。

可行性来自最后的补选规则，对每次运行都成立。期望成本来自对所有随机结果加权平均。把这两个承诺分开，就不必同时寻找一个“费用低且全部覆盖”的幸运样本。

例子与边界

三元素、八个分支的完整账本

取 $U=\{1,2,3\}$ ，

A=\{1,2\},\qquad B=\{2,3\},\qquad C=\{1,3\},

每个集合成本均为 $1$ 。分数解 $x_A=x_B=x_C=1/2$ 的值为 $3/2$ ；把三个覆盖约束相加得到 $2(x_A+x_B+x_C)\ge3$ ，所以它是最优 LP 解。整数最优为 $2$ ：一个集合总漏一个元素，任意两个集合足够。

为便于精确枚举，本例取 $\alpha=1$ ，而非使一般上界最小的 $\ln3$ 。三个独立公平随机位给出八个等概率分支。固定平局顺序 $A<B<C$ ，于是 $j(1)=A,j(2)=A,j(3)=B$ 。

初选 $R$	初始遗漏 $U_0$	实际补选集合	初选成本	追加成本	总成本
$\varnothing$	$\{1,2,3\}$	$\{A,B\}$	$0$	$2$	$2$
$\{A\}$	$\{3\}$	$\{B\}$	$1$	$1$	$2$
$\{B\}$	$\{1\}$	$\{A\}$	$1$	$1$	$2$
$\{C\}$	$\{2\}$	$\{A\}$	$1$	$1$	$2$
$\{A,B\}$	$\varnothing$	$\varnothing$	$2$	$0$	$2$
$\{A,C\}$	$\varnothing$	$\varnothing$	$2$	$0$	$2$
$\{B,C\}$	$\varnothing$	$\varnothing$	$2$	$0$	$2$
$\{A,B,C\}$	$\varnothing$	$\varnothing$	$3$	$0$	$3$

逐列求平均：

\mathbb E[C(R)]=\frac{12}{8}=\frac32,\qquad \mathbb E[C(F)-C(R)]=\frac58,\qquad \mathbb E[C(F)]=\frac{17}{8}.

若按每个遗漏元素各收一次最便宜集合费用，空分支会把 $A$ 收两次，因此元素收费的期望为 $6/8$ ，严格高于实际补选的 $5/8$ 。这正是证明中必须用不等号的位置。

任一固定元素遗漏概率为 $1/4$ ，但“至少有一个元素遗漏”的概率为 $1/2$ 。前者不是全覆盖事件的失败概率。最终八个分支全都可行，却有一个分支成本为 $3$ ，所以可行性不会让每次结果都等于整数最优。

期望、相关性与问题结构

$\mathbb E[C]\le B$ 不能直接推出每次 $C\le B$ 。对 $B>0,t>0$ ，非负成本可由 Markov 不等式得到 $\Pr(C>tB)\le1/t$ ；这通常只是粗概率界。上面的补选不需要独立的遗漏事件，而初选概率乘积确实需要独立选择集合。只知道各集合的边缘概率相同，还不足以复用这段证明。

集合覆盖通过增加集合修复可行性；容量限制的装箱或路由问题可能需要删除冲突对象并计入损失。二者的修补方向不同，不能把覆盖的成本分析直接搬过去。

推论与应用

向量松弛的相关舍入

给定共同空间 $\mathbb R^d$ 中的单位向量 $v_1,\ldots,v_n$ ， $d\ge1$ ，独立抽取 $g_1,\ldots,g_d\sim N(0,1)$ ，组成标准高斯向量 $g$ ，输出 $x_i=\operatorname{sign}\langle g,v_i\rangle$ 。同一个 $g$ 为所有坐标共享，因而这是一条相关舍入规则；零内积按固定约定处理，在理想连续模型下它的概率为零。Goemans–Williamson 算法选择这一接口，把夹角转成切边概率，再比较非负权 Max-Cut 的目标值；该向量分支的松弛不是 LP。

约束修补与成本

对有界独立负载，Chernoff 方法可控制单条容量约束，再用并集界控制同时违反任一约束的概率。例如多商品流按各请求的分数路径独立选择一条路径，期望边负载等于分数流，但同时控制所有边还需尾界。本页的覆盖补选则直接保证输出可行，成本单独计费。

图展示容量上限为 $2$ 的例子：分数总量 $1.7$ 不阻止独立抽样选中三项；删去一项恢复容量约束，但会改变目标值。本页集合覆盖使用增加集合的修补规则，八分支表给出相应成本账本。

集合覆盖贪心法逐轮比较单位新增覆盖成本，并给出确定性的调和数保证；本页算法先求 LP，再独立抽样和补选，以期望成本给保证。两种方法都必须处理不可覆盖实例，却使用不同的收费证明。

若给定集合的元素列表，总关联数为 $M=\sum_j|S_j|$ ，可在 $O(M+q+m)$ 次基本访问内预计算 $j(e)$ 、标记初选覆盖并生成去重后的输出，另加求 LP 的成本。这里按实数算术及独立 Bernoulli 抽样计费；有限精度概率实现还需说明误差。条件期望去随机化也要提供能高效计算的估计量，不能把存在性证明自动当作多项式实现。

参考资料

Deeparnab Chakrabarty, Randomized Rounding: Set Cover and Independent Set, Dartmouth lecture notes, revised 2022-01-14，pp. 1–3 的集合覆盖 LP、Theorem 1 与 Claims 1–3。
Prabhakar Raghavan and Clark D. Thompson, “Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs,” Combinatorica 7, 1987, pp. 365–374。
David P. Williamson、David B. Shmoys，The Design of Approximation Algorithms，2011，§§1.7、6.2：LP 独立抽样与向量松弛的随机超平面接口。

形式陈述 ​

输入、抽样与补选 ​

期望成本定理与证明 ​

从分数成本到近似保证 ​

三元素、八个分支的完整账本 ​

期望、相关性与问题结构 ​

向量松弛的相关舍入 ​

约束修补与成本 ​

反向链接