随机舍入

分数坐标天然给出离散选择的边缘概率，因此线性目标的期望会原样保留；困难在于许多约束必须在同一次抽样中共同成立。浓缩控制单条负载，并集界、依赖舍入或 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；真实失败概率若本身难算，逐位比较条件概率并非多项式算法。存在性证明与可实现去随机化需分开。

从分数解走到离散近似解要同时跨过两道门：目标值落在允许范围内，全部约束也在同一次抽样中成立；重试、去随机化或 alteration 解决的是第二道门失败后的处置，而不是重新证明第一道门。

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