动机
分数解可以把一个单位的覆盖量分摊给许多集合,而真正的覆盖必须整个地选取集合。独立的随机选择让分数值来指导这一决定。其中的核心矛盾在于:代价便宜的随机选择可能漏掉某个元素,因此我们必须同时控制期望代价与可行性。重复进行选择,并对未被覆盖的元素显式地加以修补,就得到一个完整的算法,而不只是一个高概率的建议。
定义
定义 4.1.1
(集合覆盖及其分数松弛)
设 是含有 个元素的有限全集,并设 ,其代价为 。假设每个元素至少属于一个集合。覆盖是指并集等于 的一族集合。分数松弛问题是:在对每个 满足 且 的约束下,最小化 。设 为任一可行的分数解,并令 ;最优分数解的代价不会高于最优整数覆盖的代价,因为每个整数覆盖都给出一个可行的零一解。
定义 4.1.2
(带修补的随机舍入)
固定整数 。对每个集合 独立地以概率 选取它。等价地,进行 次独立试验,每次的选取概率为 ,只要至少一次成功就保留该集合。之后,对每个未被覆盖的元素,加入一个包含它的代价最低的集合。重复的集合只计一次费用。由可覆盖性假设,这一修补步骤是良定义的。
定理
定理 4.1.3
(带修补的舍入的覆盖性与代价)
该算法总是返回一个覆盖,其期望代价至多为 。特别地,当 时取 ,期望代价至多为 ;因此当 为最优分数解时,期望代价至多是最优整数覆盖代价的该倍数。当 时,取 得到界 。
定理 4.1.4
(修补之前的高概率覆盖)
对任意可行的分数解,随机选择之后至少有一个元素未被覆盖的概率至多为 。特别地,对 ,取 可使该概率至多为 。
证明思路
证明
(并集界、线性性与修补的记账)
对固定的元素 ,由各集合的选择相互独立,得
这里用到当 时 ;该公式对 的情形同样成立。把这些概率对所有元素求和,就证明了并集界。不同元素对应的事件之间无需相互独立。
集合 被选中的概率至多为 ,这是对它的 次试验使用并集界的结果。因此由期望的线性性,无论各集合之间如何重叠,初始代价都以 为界。设 为包含 的最便宜集合的代价。由于所有这类集合的代价都至少为 ,分数可行性给出
实际的修补代价至多为 ,其中 是“ 最初未被覆盖”的示性变量;即使一个新加入的集合同时修补了多个元素,这仍然是一个上界。取期望后得到至多 。把两个界相加即证明了定理。修补使可行性成为必然;期望代价的保证并不是对每一种结果都成立的确定性上界。
证明透视
线性性的两种用法
期望代价是对集合求和,而期望修补代价是对元素求和。两个计算都不要求这些代价项相互独立。独立性在更早的步骤中使用,即用来分解“包含某个固定元素的所有集合都未被选中”的概率。
例题详解
例题 4.1.5
(集合构成的三角形)
设 ,三个单位代价的集合为 、 和 。令每个 是可行的,此时 。取 ,每个集合被选中的概率为 。每个元素被漏掉的概率为 。期望初始代价为 ;一般的修补界为 ,因为每个最便宜的覆盖集合代价为一。因此期望总代价至多为 。真正的最优整数代价为 。
例题 4.1.6
(被迫的选择)
若元素 恰好只属于一个集合 ,则可行性与 迫使 。对任意正的 ,舍入都以概率一选取 。若认为每个元素的失败概率恰好等于 ,那就错了:那只是一个统一的上界,不是等式。
例题 4.1.7
(选取失败概率目标)
对 和 ,取 即足够。修补之前出现任何未覆盖元素的概率至多为 。随后修补使每次运行都得到一个覆盖。该定理控制的是期望代价;它并不断言每次运行的代价都至多为 。
常见错误
反例模式
每个分数只舍入一次可能失败
在三角形的例子中只做一次试验时,包含元素 的两个集合都未被选中的概率为 。因此对可行线性规划解进行独立舍入并不会自动产生一个覆盖。重复试验降低失败概率,而修补则消除剩余的不可行风险。
常见错误
(期望代价不是每次运行的保证)
期望代价与失败概率是两个独立的陈述。仅有较小的期望代价,并不能保证某一次具体运行的代价低;而较小的失败概率,也不会使未覆盖的结果变成可行。此外,线性规划下界要求问题是最小化问题且代价如所设为非负;近似保证的方向必须对照该下界来核对。
为什么会出现对数
对单个元素而言,界 随独立试验次数指数下降。为使全部 个元素同时有很大把握被覆盖,并集界把它乘以 。取 与 同阶,恰好抵消这个因子。这就是证明中对数的来源;它并不是说每个具体实例都需要这么多次试验。在被迫选择的例子中,一次试验就能确定地覆盖该特殊元素。并集界把所有元素都当作具有最坏允许的失败概率,因而可能相当松。
线性规划还提供了一个在运行舍入之前就有用的数值证书。对任何整数覆盖,把被选集合的 取为 、其余取为 ,就得到代价相同的可行分数点。因此,分数最优值的任何下界都是每个整数覆盖代价的下界。然而,任意一个可行的分数点只是分数最优值的上界,并不自动成为整数最优值的下界。因此,与整数最优值的近似比较要用到最优分数解(或另行证明过的对它的近似);相对于 的代价界则对每个可行分数点都成立。
例题 4.1.8
(分数可行并不意味着最优)
设 ,取两个都等于 的集合,代价分别为 和 。选择 是分数可行的,且 ,而整数最优代价与分数最优代价都是 。舍入定理仍然以 来界定期望代价,但若代入 就是错误的。选取最优线性规划解才能使该比较成立。
独立性、修补与实现
一种实现方式是为每个集合抽取一个概率为 的独立伯努利(Bernoulli)变量。等价的重复试验描述是一种证明工具,也是实现同一分布的方式:属于不同集合的各次试验必须全部相互独立。两个元素未被覆盖的事件一般并不独立,因为同一个随机选出的集合可能同时包含这两个元素。并集界有意避免了需要它们的联合分布。例如,若一个集合同时包含两个元素,则未选中它会使两个元素同时未被覆盖。
修补可以这样实现:在随机选择之后扫描全集,然后为每个仍未被覆盖的元素加入一个最便宜的、包含它的可用集合。证明为每个最初未被覆盖的元素至多计入 。如果先前的修补恰好也覆盖了之后的某个元素,那么对后者的计费可能是不必要的,但无论如何计入仍保持为上界。因此分析不依赖于修补的顺序。代价非负保证了把一个加入的集合重复计算不会低估真实代价;重复的集合只需存储一次。
理想化的证明假定概率精确且线性规划解最优。在实际实现中,必须说明所用的算术、求解器容差与随机比特模型。一个可行且近似最优的分数向量仍可用同样的证明进行舍入,其目标值为其实际值 ;若要得到相对于整数最优值的指定近似因子,还需要对该值有已证明的界。对一个近似可行的向量,若不先修正违反的约束就进行舍入,则 的估计不能成立:每个元素所关联的各分数之和必须如假设那样至少为一。
修补估计可以改进为 ,而不是 。这一更精细的形式直接来自期望的线性性,在具体实例上可能小得多。较粗的界则使近似因子仅依赖于 与线性规划值。例如,若所有元素都有便宜的集合可用,但分数解还为其他昂贵的集合付费,那么 可以远低于 。
一个有用的概率计算
当需要明确的失败阈值时,应以正确的方向使用概率界。例如,若 而期望的上界为 ,则只需 。取整数上取整得 ,且 。这是一个充分的选择,而不是证明在某个具体实例上十三次试验不可能。实际概率可能小得多,因为分数约束可能有松弛,或者因为失败事件之间高度重叠。
另外的马尔可夫(Markov)界可以把期望陈述转化为代价的尾部陈述。由于总代价 非负,对任意 有 。因此,以至少 的概率,修补后的覆盖代价至多为 (边界情形可无害地照此理解)。这个结论在常数上比期望代价的保证更弱,但它给出了单次运行的概率。如果 ,成本非负且期望界为零,所以成本几乎必然为零;此时无需在零阈值处应用马尔可夫不等式。独立重复可以降低所有运行都超过阈值的机会;选取修补后代价最低的覆盖仍保持可行性。重复之间的独立性必须加以安排,且在实现中必须计入生成这些重复的代价。
对随机结果的确定性检查
随机选择一旦完成,检查输出是否为覆盖就不再需要任何概率计算。扫描被选中的集合,标记它们包含的每个元素,并验证所有元素都被标记。只要输入满足可覆盖性假设,且最便宜的包含集合被正确找到,修补步骤就保证这一检查会通过。如果输入中有元素不属于任何可用集合,则原实例没有可行覆盖,其分数约束也不可行;修补定理有意排除这种情形。
常见错误
(同一个近似陈述中的两种不同比较)
近似陈述包含两个不同的比较。第一,输出代价的数学期望以提供给舍入的分数点的目标值的一个倍数为界。第二,最优分数值以最小整数覆盖代价为上界。第二个比较用到可行集合之间的包含关系:所有整数覆盖都产生分数可行点,而松弛问题可能还有额外的分数点。弄混哪一个可行集合更大,就会使结论反向。分数最优值可以严格更小,如在三角形例子中它至多为一又二分之一,而最便宜的整数覆盖代价为二。
随机选择规则也有直观的极限情形。当某个分数变量为零时,其集合在舍入过程中永远不会被选中,但若它对某个未被覆盖的元素而言是最便宜的,修补仍可能把它加入。当某个变量为一时,其集合以概率一被选中。对中间值,概率随试验次数增加而增大,但永远不超过一。若直接把 当作概率,则只要该数超过一就会失效。它作为实际概率的上界仍然有效,而期望代价的证明正是这样使用它的。
该定理假设代价非负。如果允许负代价的集合,多选一个集合可能降低总代价,而对某个集合重复计费可能使修补论证中的不等式反向。人们可以通过先选取负代价集合并修改实例来预处理这样的不同模型,但那需要另行分析。在这里,代价非负的假设使每个部分和都可以由整个分数目标值界定,并使修补代价的比较一目了然。
总结
随机舍入把分数隶属度转化为独立的集合选择。指数衰减界定漏掉某一元素的概率;并集界控制全部元素;最便宜集合的修补则带来确定的可行性以及对数级的期望近似界。
练习
快速检查
(在三角形例子中,当 时,求没有任何集合被选中的概率。)
每个集合不被选中的概率相同。
解答 · 答案
每个集合各自以概率 不被选中,且相互独立,所以概率为 。
快速检查
(若 且 ,给出任何元素未被覆盖的概率的并集界上界。)
使用高概率覆盖定理中的界。
解答 · 答案
至多为 。该界不必是紧的。
快速检查
(即使“各元素被覆盖”的事件相互依赖,为什么仍可以把被选中集合的期望代价相加?)
期望的哪一条性质不需要独立性?
解答 · 答案
期望的线性性无需独立性即成立。集合选择的独立性用于界定漏掉某个固定元素的概率,而不是用于把期望代价相加。
快速检查
(设 ,且 是分数松弛问题的最优解。当 时,给出该定理的期望近似因子。)
把 、 代入 。
解答 · 答案
该界为 。由于分数最优值至多等于整数最优值,同一个数也就是期望近似因子。