【算法分析与设计】第24篇：随机化舍入与线性规划松弛

第20篇中我们讨论了NP困难问题的近似策略第23篇展示了随机性如何成为算法设计的利器。本篇将两种思想熔于一炉先松弛后舍入。面对一个整数规划问题我们暂时“忘记”变量必须取整的约束允许它们取实数在扩大的可行域中用线性规划高效求解然后通过随机化手段将分数解“舍入”为整数解并证明舍入不会过度损害目标值。这套方法论在近似算法设计中占据核心地位其威力在集合覆盖、设施选址、最大可满足性等问题上得到了充分验证。一、整数规划与线性规划松弛许多组合优化问题可以自然地表述为整数规划在若干线性约束下最小化或最大化一个线性目标函数且决策变量限定为整数通常是0或1。以顶点覆盖问题为例其整数规划形式为minimize∑v∈Vxvsubject toxuxv≥1,∀(u,v)∈Exv∈{0,1},∀v∈Vminimizesubject to​v∈V∑​xv​xu​xv​≥1,∀(u,v)∈Exv​∈{0,1},∀v∈V​其中 xv1xv​1 表示顶点 vv 被选入覆盖。整数约束 xv∈{0,1}xv​∈{0,1} 使问题成为NP困难的——正是在0和1这两个孤立的取值之间问题的难度陡然上升。线性规划松弛的策略直截了当将 xv∈{0,1}xv​∈{0,1} 替换为连续约束 0≤xv≤10≤xv​≤1。约束变为连续的线性不等式可行域从离散点集扩展为凸多面体问题退化为一个标准线性规划可在多项式时间内用内点法或单纯形法求解。松弛后得到的分数最优解记为 x∗x∗其目标值 OPTLPOPTLP​ 必然不劣于原整数最优解的目标值 OPTOPT——因为整数可行域是松弛后可行域的子集。对于最小化问题有 OPTLP≤OPTOPTLP​≤OPT。这个松弛解本身通常不是可行的整数解但它提供了两个关键资产一个下界对于最小化问题以及舍入操作的“概率指南”。二、随机化舍入的基本原理随机化舍入的核心思想非常自然将松弛解 xi∗∈[0,1]xi∗​∈[0,1] 解释为“变量 ii 应取1的概率”。具体而言独立地以概率 xi∗xi∗​ 将每个变量设为1以概率 1−xi∗1−xi∗​ 设为0。这一舍入方式保证了 E[xi]xi∗E[xi​]xi∗​从而期望目标值等于 OPTLPOPTLP​。然而独立舍入可能导致某些约束被违反。例如在顶点覆盖中边 (u,v)(u,v) 的约束 xuxv≥1xu​xv​≥1 在舍入后可能被破坏——xuxu​ 和 xvxv​ 同时被舍为0的概率为 (1−xu∗)(1−xv∗)(1−xu∗​)(1−xv∗​)。由于松弛约束保证 xu∗xv∗≥1xu∗​xv∗​≥1该概率至多为 1/41/4当 xu∗xv∗1/2xu∗​xv∗​1/2 时取到。这意味着每条边以 ≤1/4≤1/4 的概率未被覆盖。处理这类约束违规有两种策略一是调整舍入概率引入变量之间的相关性以保护约束二是在舍入后进行修补——额外选择一些变量强行设为1以确保所有约束满足并分析修补带来的额外成本。集合覆盖问题恰好完美地展示了后一种策略。三、集合覆盖的随机化舍入与近似比分析集合覆盖问题是展示随机化舍入全流程的理想案例。给定全集 U{e1,…,en}U{e1​,…,en​} 和子集族 S{S1,…,Sm}S{S1​,…,Sm​}每个子集 SjSj​ 附有成本 cj≥0cj​≥0。目标是选择总成本最小的子集子族使其并集覆盖 UU 中所有元素。该问题的整数规划形式为minimize∑j1mcjxjsubject to∑j:ei∈Sjxj≥1,∀ei∈Uxj∈{0,1},∀jminimizesubject to​j1∑m​cj​xj​j:ei​∈Sj​∑​xj​≥1,∀ei​∈Uxj​∈{0,1},∀j​松弛 xj∈[0,1]xj​∈[0,1] 后求解得分数最优解 x∗x∗。定义问题的频率fmax⁡ei∈U∣{j:ei∈Sj}∣fmaxei​∈U​∣{j:ei​∈Sj​}∣即包含任意单个元素的子集数量的最大值。舍入策略将每个子集 SjSj​ 以概率 xj∗xj∗​ 独立地选入解中。此时期望成本为 ∑cjxj∗OPTLP≤OPT∑cj​xj∗​OPTLP​≤OPT。但元素 eiei​ 未被任何选中子集覆盖的概率为Pr⁡[ei 未覆盖]∏j:ei∈Sj(1−xj∗)≤∏j:ei∈Sje−xj∗exp⁡(−∑j:ei∈Sjxj∗)≤e−1Pr[ei​ 未覆盖]j:ei​∈Sj​∏​(1−xj∗​)≤j:ei​∈Sj​∏​e−xj∗​exp​−j:ei​∈Sj​∑​xj∗​​≤e−1最后一步利用了松弛约束 ∑j:ei∈Sjxj∗≥1∑j:ei​∈Sj​​xj∗​≥1。因此每个元素以 ≤1/e≤1/e 的概率未被覆盖。取参数 d≥1d≥1将上述独立舍入过程重复 d⋅ln⁡nd⋅lnn 轮将各轮选中的子集取并集则元素 eiei​ 在所有轮中均未被覆盖的概率不超过 (1/e)dln⁡nn−d(1/e)dlnnn−d。由联合界所有 nn 个元素均被覆盖的概率 ≥1−n1−d≥1−n1−d。期望成本为 dln⁡n⋅OPTLP≤dln⁡n⋅OPTdlnn⋅OPTLP​≤dlnn⋅OPT。因此算法以高概率输出一个可行解其成本不超过最优解的 O(log⁡n)O(logn) 倍。这一 O(log⁡n)O(logn) 近似比在集合覆盖问题上几乎是匹配下界的——除非PNP不存在 o(log⁡n)o(logn) 的近似算法Feige, 1998。四、舍入技术的变体与技巧独立舍入是最基本的形式在约束较为松散时表现良好。当约束结构更复杂时需要更精巧的舍入策略。相关舍入不再独立地决定每个变量的取值而是成组地耦合决策。例如在设施选址问题中可以先将分数解聚类在同一簇内协调舍入确保每个客户被至少一个打开的设施覆盖。相关舍入通常能给出更好的近似比代价是概率分析更为复杂。条件期望法随机化舍入给出了存在性的概率证明——期望上存在一个不错的整数解。条件期望法可以将随机化算法去随机化在每一步确定一个变量的取值时计算两种选择下剩余随机过程的期望目标值选择期望更优的那一支。这种方法将存在性证明转化为确定性算法同时保持相同的近似比在集合覆盖问题上同样可达到 O(log⁡n)O(logn) 近似比。对偶性的角色线性规划的对偶理论在近似比证明中扮演关键角色。原问题的松弛下界与对偶可行解提供的下界往往能与舍入解的期望成本对齐形成完整的证明闭环。对偶拟合方法给出了集合覆盖的确定性贪心算法其分析本质上与随机化舍入共享同一数学核心。五、线性规划松弛的适用边界线性规划松弛加随机化舍入的范式虽然强大但并非万能。其有效性取决于两个条件一是松弛质量松弛后线性规划的最优解必须与原整数最优解足够接近。若两者差距过大即“整数间隙”大即使完美的舍入也无法给出好的近似比。某些问题具有极大的整数间隙此时需改用更强的松弛形式如半定规划松弛。二是舍入损失可控从分数解恢复到整数解的过程中目标值的膨胀必须在可证明的范围内。舍入策略的设计与近似比的分析通常需要针对问题的具体约束进行精细调整不存在“一招鲜”的通用舍入方法。六、总结与展望线性规划松弛将连续优化的高效性与组合优化的结构要求连接起来。随机化舍入则提供了一套从“软化”的分数解回到“硬化”的整数解的通用工具链。这种“先松弛后舍入”的方法论已经渗透到近似算法的方方面面从集合覆盖到设施选址从最大割到稀疏割从调度问题到网络设计。线性规划结合对偶性发挥到极致的另一条路径——对偶拟合——能为贪心近似提供与随机化舍入同样紧致的理论分析。后续篇章将在贪心近似和局部搜索等主题中进一步展示这些技术。下一篇我们将把目光转向在线算法这一特殊模型在输入逐步到来、未来完全未知的情况下算法如何在没有“后见之明”的条件下做出决策以及竞争比分析如何为在线策略提供性能保证。