动机
局部划算的购买未必带来最便宜的完整方案。集合覆盖把这个矛盾具体化:一个集合可能覆盖许多尚未满足的要求,却留下难以处理、成本高昂的剩余要求。近似分析不假装困难消失,而是证明指定的可行输出成本至多为最优值的受控倍数。
本篇在同一模型发展三种分析。贪心在首次覆盖要求时收费;线性规划容许分数购买,提供下界;原始—对偶算法同时构造覆盖与下界证书。它们的近似因子来自不同结构参数,应比较保证而不只比较程序。
定义
定义 4.3.1
(加权集合覆盖及其参数)
有限全集 有 个元素,可选集合为 ,其并集为 。集合 的有限成本 非负。所选集合并集为 时称为覆盖,成本为所选成本总和。以 表示最小覆盖成本。令 , 为任何一元素所属可选集合数的最大值。可行性保证 。
集合按标号视为不同选项,即使内容相同也可不同。成本非负,所以解无需重复选同一集合;空集合可忽略。容许零成本,保证写成不等式,避免除以可能为零的最优值。计算上可用有理成本及明列的关联数据;近似证明本身只需精确有限运算。
贪心维持未覆盖集合 ,在 的选项中,选使 最小者,再从 移去新覆盖元素。固定的平手规则均可。未完成时总有合格集合,每步至少覆盖一新元素,故最多选 次。若分母计入已覆盖元素,便是另一算法。
定义 4.3.2
(分数覆盖与对偶装填)
分数覆盖规划最小化 ,条件为
对偶装填规划最大化 ,条件为
把分数的符号约束换成 ,便得精确的整数规划表述。整数覆盖提供这种可行的零一向量 。可行对偶为每元素指定非负价格,而不让任何可选集合的总元素价格超过成本。
以下不需要强对偶定理,会直接证明下界性质。计算最优分数解是另一最优化任务;舍入定理假设已提供该解,并未实现线性规划求解器。
概念视角代数
两个参数就是行和与列和
设 为 - 关联矩阵,当 时 。则 是最大的列和, 是最大的行和。原问题是 ,约束为 ;对偶问题是 ,约束为 。
定理 / 命题
定理 4.3.3
(调和贪心近似)
令 。贪心覆盖成本至多为 ,因而至多为 。更强地,其成本至多为分数最优值的 倍。
定理 4.3.4
(频率舍入及原始—对偶算法)
对任何可行分数覆盖 ,选取全部 的集合可得覆盖,成本至多 。另有直接构造覆盖及可行对偶 的算法,使成本至多 ,无需先求解分数规划。
证明思路或证明
证明
(弱对偶性)
先证弱对偶。任意可行分数覆盖 及可行对偶 ,由非负性及两类约束,有
中间等式只是重排有限的元素—集合关联和。因此每个可行对偶值都是每个覆盖成本的下界。即使不知道最优解,也可用简单不等式检查这张证书。
对贪心购买收费
证明
(以分摊与弱对偶证明贪心)
贪心以成本 覆盖 个新元素时,每个新元素收费 。每元素只收一次,全部费用总和恰等于所选总成本。集合可重叠;此规则避免同一元素因重叠而在账目重复付款。
固定任意大小 的非空可选集合 ,不要求它被选。按首次覆盖时间排列其元素,同一步中的平手任意排列。在覆盖其第 元素的那次选择之前, 至少还有 个未覆盖元素。当时 也是合格方案,因此贪心比率及元素费用满足
相加得 。所以 对全部集合约束均可行,包括空集合。弱对偶给出
其中 为分数最优值。最后一式是因为最小化问题中,整数可行解只是分数可行解的子集。也可与任意分数可行成本比较,避免假定最优解存在;本模型其实存在最优解,因为把每个坐标截于一不会破坏可行性或增加成本,留下紧致可行域。
由 得较弱的 版本。对 , 单调递减,所以 ,相加便得 。这是最坏保证,不表示每个输出达到该界。若最优值为零,同一组非负不等式也迫使贪心成本为零。
门槛舍入用频率而非集合大小
证明
(门槛舍入覆盖每个元素)
取可行分数覆盖 ,固定元素 。它最多属于 个集合。若这些坐标全严格小于 ,总和便严格小于一,违反覆盖约束。因此至少一个包含它的集合被门槛规则选中,对全部元素皆如此。
对每个选中 ,,所以 。先对选中者相加,再用成本非负加入未选项,便得成本界。门槛须包含等号;排除恰为 的坐标,可能漏覆盖元素。即使分数解成本高,仍可舍入,但只有最优或近乎最优分数解,才提供相应的整数最优比较。
与 描述不同结构。一集合可很大,但每元素只属两集合;也可每集合很小,却有一元素出现在许多集合。调和保证受最大集合大小控制,门槛与下面的直接构造受最大元素频率控制,不能在证明中任意互换。
一边建覆盖,一边提高对偶价格
证明
(原始—对偶构造)
起初 ,未选任何集合。尚有未覆盖元素 时,只提高 ,直到某包含它的集合紧约束,即元素价格总和等于其成本。选一个这种集合,标记其全部元素已覆盖。若合格集合已紧,便不加价而直接选取;零成本不造成除法或进展问题。
提高的数值可明确计算:对每个包含 的集合,求非负松弛量 ,提高其最小值。至少有一个这种集合,成本有限,不含 的约束不变,包含者的松弛量恰减去该值,故不会变负,且至少一个变紧。对偶可行性因而保持。
已选集合不包含任何当前未覆盖元素,所以提高 不改变它们的总价,每个已选集合到终止时仍紧。每次至少覆盖一新元素,最多 步。完成时
证明只需价格可行、所选约束紧及频率界,从未声称所构造对偶最优。事后删去多余集合可减少成本,却不是保证所必需。
证明透视
两种证书的不等式方向相反
可行覆盖给出最优值的上界,可行对偶给出下界;每个分析都把前者与后者的受控倍数联系起来,但各假设用在不同的地方。贪心要求每个集合 在先前每一步都是合格的备选,由此得到 ,再用 缩放以恢复对偶可行性。原始—对偶构造每一步保持可行:只把一个价格抬高到最小松弛量为止;并使已选集合保持紧,因为只有未覆盖元素的价格才会改变。其最后计算的关键一步是交换对集合与元素的求和次序:紧性把成本化为 ,频率界再把这个个数化为因子 。每个不等式都用到成本与价格的非负性;缺少它,与 的比较便不成立。
例题详解
例题 4.3.5
(贪心可能付三,最优只需二)
取 ,单位成本集合 、、。贪心先选 ,比率 小于 ;其后五、六迫使再选 ,成本三。但 已能以二覆盖全部,且五只在 、六只在 ,两者必需。对偶 、其余零可证下界二。局部划算未保持精确最优。
例题 4.3.6
(分数三角形与舍入落差)
,三个二元素子集各成本一。整数覆盖需两集合。各设 ,分数成本 ;各元素价格 对偶可行且同值。弱对偶证明分数值最优。此时 ,门槛舍入选全部三集合,成本三恰为分数值两倍,而整数最优只有二。同一实例的不同合法算法可以质量不同。
例题 4.3.7
(三角形上的直接原始—对偶执行)
同一实例由零价格开始,选未覆盖 并加到一。、 均变紧,选 。只余 ,但 已紧,无需改价即可选。覆盖成本二,可行对偶值一,符合二倍保证,而此整数输出其实最优。算法证明不要求对偶也最优。
反例模式
不能随意把门槛改成严格不等式
分数三角形的全部坐标恰为 。若只选严格大于 者,就没有任何集合,什么也没覆盖。修正是已证的 ,包含等号。浮点容差需要另有理由的可行性修补,数学门槛证明不会自动保证任意数值实现。
常见错误
常见错误
(把松弛的界方向弄反)
最小化松弛给下界,最大化松弛给上界,反向会破坏近似比证明。可行对偶也须满足每个集合约束,而不只是被选者。未缩放的贪心费用一般违反部分约束,这正是调和缩放的用途。
常见错误
(抬高已覆盖元素的价格)
原始—对偶证明依赖不提高已覆盖元素的价格;否则可破坏既选集合的紧性或约束。重叠无害,是因为最后明确用 限制重数,并未假定所选集合互不相交。
总结
收费把贪心比率在调和缩放后转成对偶可行下界。频率舍入把分数覆盖变成整数覆盖。直接原始—对偶方法在构造期间保持可行性及紧性。这些论证展示局部选择、松弛与下界如何建立严格近似保证,而非宣称精确最优化。
练习
快速检查
(若每个可选集合最多三元素,明确写出调和保证,并与按整个全集大小的界比较。)
计算 ,并注意 。
解答 · 答案
,所以贪心成本至多最优的 倍;若 ,可用更小的 。由 ,不会比 差。全集可以很大,集合仍很小。
快速检查
(在分数三角形,为何全设 虽非负,却不是合法对偶?)
检查某个二元素集合的约束。
解答 · 答案
每个二元素集合价格总和为二,超过成本一。非负只满足符号条件,所有集合上界仍须成立。缩至每个一半便得例题的最优可行对偶。
快速检查
(把有限无自环图的加权顶点覆盖建模为集合覆盖,推出二倍门槛舍入;处理孤立顶点及无边情形。)
先选定全集、集合及其成本,再求频率 。
解答 · 答案
以边为全集,每顶点对应其全部关联边的集合,成本为非负顶点权。每边恰属两集合,所以 。分数顶点覆盖在每边的两端值之和至少一,选全部值至少一半的顶点便覆盖每边,且成本至多分数目标两倍。孤立顶点对应空集合,可不选;若无边,空选已是零成本最优,另行处理,不套用本篇 约定。
快速检查
(可行实例中成本全部为零,解释两算法的终止及目标界。)
考察所有成本为零时的贪心比率与紧约束。
解答 · 答案
贪心总能选合格的零比率集合,每步覆盖一新元素,最多 步、成本零。原始—对偶的零价格使全部约束已紧,每步无加价便选包含未覆盖元素的紧集合,同样有进展并以零成本终止。不等式仍有效,直接除以 OPT 却不合法。