随机舍入

基本舍入 ​

线性规划给 $x_i\in [0,1]$。最简单独立舍入令 $X_i\sim \mathrm{Bernoulli}(x_i)$，输出选择集 $\{i:X_i=1\}$。线性目标保持期望：

$$\mathbb{E}\sum _i{c}_i{X}_i=\sum _i{c}_i{x}_i.$$

这只控制平均目标，不保证每条约束同时满足。

约束与概率 ​

对负载 $\sum _i{a}_{ji}{X}_i$，若项独立且有界，可用 Chernoff 控制超过容量的概率；再用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。覆盖所有约束。若总失败概率小于 1，概率方法证明存在好舍入；可按条件期望公理库条件期望Conditional expectation相对于子 σ-代数可测并保持其事件上积分的随机变量。逐个固定随机位，保持坏事件势函数不增，实现去随机化。另一策略 alteration 先独立舍入，再删除造成冲突的对象并计损失。

路由拥塞例子 ​

多商品流 LP 把一条请求分数地分散到多条路径。按路径流量占比为每个请求随机选一条路径，期望边负载等于 LP；当单请求贡献受限时，Chernoff 给边拥塞尾界。所有边都安全需要共同概率，而不是对每条边单独说“高概率”。

失败边界 ​

$\mathbb{E}[cost]\le \alpha OPT$ 不能推出高概率近似；Markov 只能给粗常数概率。共享资源造成强相关时独立舍入方差可能过大，需要 dependent rounding 保持边缘概率与负相关。舍入尺度、重试/修补导致的目标损失和 LP 数值误差都应计入保证。

缩放与 alteration ​

Set cover 舍入常先把概率放大到 $p_i=min\{1,c{x}_i\}$，使每个元素未覆盖概率指数下降，再对仍未覆盖元素补选一个集合。放大增加期望成本，补选再增加 alteration 成本；近似比来自两项的共同上界，不是原 LP 目标自动保持。

条件期望去随机化要选择一个可有效计算的 pessimistic estimator；真实失败概率若本身难算，逐位比较条件概率并非多项式算法。存在性证明与可实现去随机化需分开。

从期望到可行解的两道门 ​

设覆盖约束为 (\sum_{i\in A_j}x_i\ge1)，独立舍入 (X_i\sim\operatorname{Bernoulli}(x_i)) 时，目标成本满足 (\mathbb E[c^TX]=c^Tx)，但某条约束失败概率约为 (\prod_{i\in A_j}(1-x_i))，不一定足够小。把概率放大为 (\min(1,\alpha x_i)) 可降低失败率，却把期望成本同时乘上 (\alpha)。

因此完整流程必须分别回答：

1. 每个随机变量如何从分数解生成；
2. 目标值怎样集中在允许倍数内；
3. 所有约束同时满足的概率是多少；
4. 失败时是重试、条件期望去随机化，还是 alteration 修复。

边际概率相同不等于联合分布相同。独立舍入方便用 Chernoff，却可能破坏“恰选 $k$ 个”或 matroid 约束；dependent rounding 通过负相关和总量保持换取可行结构，证明不能继续假设变量独立。

参考资料

• Prabhakar Raghavan, Clark Thompson, Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs, Combinatorica, 1987.
• Prabhakar Raghavan, Probabilistic Construction of Deterministic Algorithms, JCSS, 1988.