最小权重次模覆盖

最小集合覆盖¶

首先, 我们来看一下最小权重集合覆盖, 输入是一个包含所有元素的全集\(\mathcal{U}\), 一系列包含了部分\(\mathcal{U}\)中元素的子集\(\mathcal{S}\), 以及一个为每个子集指定成本(权重)的函数\(w\). 目标是从\(\mathcal{S}\)中选出一些子集, 使得这些子集的并集等于全集\(\mathcal{U}\), 并且这些子集的权重之和最小.

最小集合覆盖是一种特殊情况, 即假设所有子集的权重都是\(1\), 再这种情况下, 因为每个子集的权重相同, 所以我们只需要选出最少数量的子集即可.

我们可以使用一个简单的贪心算法来解决上述问题. 首先, 初始化一个空的子集\(\mathcal{C}\), 这个集合将用来存放我们最终选出的子集. 然后, 设定循环条件, 只要\(C\)中的所有子集的并集还没能包含所有元素\(\mathcal{U}\), 就继续选. 在每次循环中, 在所有可选的子集中, 找出那个能够覆盖最多新元素的子集. 将这个最有效的子集\(S\)加入到我们的解集\(\mathcal{C}\)中, 当循环结束的时候, 返回\(\mathcal{C}\)作为最终的解.

虽然贪心算法不一定能找到绝对最优解, 但是它能给出一个足够好的近似解, 设\(\mathcal{X}_i\)为算法经过\(i\)次迭代后已经覆盖的元素集合, 满足\(|\mathcal{X}_i|\geq |\mathcal{U}|\times (1-(1-\frac{1}{OPT})^i)\).

证明: 我们先做一个问题的转换, 将当前的最小集合覆盖问题转换为一个最大覆盖问题的实例. 新实例: 从集合\(S\)中挑选出\(OPT\)个集合, \(OPT\)是原问题最优解所用的集合数量, 目的是最大化这\(OPT\)个集合所覆盖的元素数量. 这个问题的最优覆盖数量是\(|\mathcal{U}|\), 此时, 应用一个上周关于最大覆盖问题贪心算法的已知性能保证: 对于最大覆盖问题, 贪心算法在选择\(i\)个集合后, 其覆盖的元素数量至少为最优解覆盖数量的\((1-(1-1/k)^i)\)倍. 在我们的新实例中, \(k\)就是\(OPT\), 将这些值带入到上述性能保证公式, 我们就能得到11.1.

GREEDY-CARDINALITY算法是一个\(\ln |\mathcal{U}|\)近似算法, 即它在\(\lceil \ln |\mathcal{U}|\rceil\times OPT\)次迭代之后必然会终止, 即覆盖所有元素.

证明: 从刚才推导出的不等式\(|\mathcal{X}_i|\geq |\mathcal{U}|\times (1-(1-\frac{1}{OPT})^i)\)开始, 我们将迭代次数\(i\)设置为\(\lceil \ln |\mathcal{U}|\rceil\times OPT\), 并带入这个公式, 得到: \(|\mathcal{X}_{\lceil \ln |\mathcal{U}|\rceil\times OPT}|\geq |\mathcal{U}|\times (1-(1-\frac{1}{OPT})^{\lceil \ln |\mathcal{U}|\rceil\times OPT})\), 经过化简, 我们可以得到: \(|\mathcal{X}_{\lceil \ln |\mathcal{U}|\rceil\times OPT}|\geq |\mathcal{U}|-1\).

最小权重集合覆盖¶

与刚才的集合覆盖问题不同, 权重版本给每个集合赋予了一个成本或者权重\(w(S)\). 目标是选择一个子集族\(\mathcal{C}\), 使其能够覆盖所有的元素, 同时这些被选中集合的总权重最小.

为了得到一个好的近似解, 算法不能再像之前那样只看哪个集合能够覆盖最多的新元素. 它必须将成本考虑进去. 一个很自然的想法是, 在每一步, 选择性价比最高的集合, 这里的性价比或者成本效益被定义为, 为了覆盖每一个新的元素所需要付出的平均成本, 算法在每一步都会计算所有候选集合的这个值, 并选择那个值最小的集合.

定理11.1: 该算法是一个\(H_{\Delta}\)-近似算法, 其中\(\Delta = \max_{S\in \mathcal{S}}|S|\), 它表示的在所有候选的集合中, 尺寸最大的那个集合的大小. \(H_n\)是调和书, \(H_n = 1+1/2+1/3+....+1/n\), 它是一个数列的和, \(H_{\Delta}\)就是以最大集合尺寸\(\Delta\)作为下标的调和数, \(H_n\)的值和\(\ln(n)\)近似, 它随着\(n\)对数增长. 这意味着\(H_{\Delta}\)是一个相对较小的数, 说明这个近似算法的性能还行.

证明: 我们会使用一种叫做记账法的策略来证明这个定理. 首先, 我们来看什么是账单, 每个元素都有一个账单, 而且是在它被首次覆盖的那一刻被赋予一个账单. 而成本, 集合作为一个整体, 它只有成本, 也就是\(w(S)\), 它没有账单. 当贪心算法运行的某一刻, 某个集合\(S\)被选中, 因为它当时的性价比最高, 假设元素\(j\)正是在这一刻被集合\(S\)首次覆盖的, 那么\(j\)的账单就被永久地确定为\(bill(j)=\) \(S\)地成本\(/S\)在当时能提供的新元素数量, 这个值, 正好就是算法选择\(S\)的时候所看中的那个性价比数值, 即它的账单. 将所有元素的账单加起来我们可以得到贪婪算法的总权重\(\mathcal{greedy} = \sum_{j\in \mathcal{U}} bill(j)\).

现在, 我们要证明对于最优解\(\mathcal{O}\)中的任意一个集合\(O\), 其内部所有元素的账单总和\(\sum_{j\in O} bill(j)\)不会超过\(H_{\Delta} w(O)\), 如果能够证明这个, 我们就能最终证明整个贪心算法的近似比.

为了分析贪心算法的成本, 我们引入一个参照物 -- 最优解, 设\(\mathcal{O}\)代表一个最优解, 它是一个集合的集合, 我们从最优解\(\mathcal{O}\)中任意挑选一个集合出来进行分析, 假设它有\(l\)个元素, \(O = \{o_1, o_2, ..., o_l\}\). 我们假设贪心算法是按照\(o_1, ..., o_l\)这样的顺序来覆盖掉\(O\)中的这些元素的. \(o_i\)是\(O\)中第\(i\)个被贪心算法覆盖的元素, 设\(A_i\)为贪心算法选择的, 首次覆盖了元素\(o_i\)的那个集合, 如文章图中, \(A_1\)首次覆盖了\(o_1\), \(A_2\)首次覆盖了\(o_2\)和\(o_3\), 所以\(A_3=A_2\). 设\(X_i\)为在选择\(A_i\)前, 所有已经被覆盖的元素的集合.

由于算法的贪心性质, 我们可以得到:

\(\frac{w(A_i)}{\left|A_i \setminus X_i\right|} \le \frac{w(O)}{\left|O \setminus X_i\right|} \le \frac{w(O)}{\left|\{o_i, \dots, o_l\}\right|} = \frac{w(O)}{l - i + 1}\)

首先, 我们来看左边的这个不等式, 这是由贪心算法的本质所决定的, 在算法选择\(A_i\)的那一刻, 它考察了所有尚未被选中的候选集合, \(A_i\)之所以被选中, 是因为它的性价比(成本/提供新元素的数量)是所有候选者中最低的, 在那一刻, 最优解中的集合\(O\)也是一个候选者(或者说\(O\)中的元素还有没有被覆盖的), \(O\)当时的性价比是\(w(O)/|O \setminus X_i|\). 因此, \(A_i\)作为冠军, 它的性价比必然小于等于任何其他对手, 包括\(O\), 这就证明了左边的不等式.

其次, 我们来看右边的这个不等式, 按照我们的分析顺序, 当要覆盖\(o_i\)的时候, \(o_1, ..., o_{i-1}\)已经被覆盖了, 而\(o_i, ..., o_l\)这些元素还没有被覆盖. \(|O\setminus X_i|\)表示的是算法在选择\(A_i\)之前, \(\mathcal{U}\)中所有已经被覆盖的元素的集合, 这可能是比\(o_i, ..., o_l\)更大的一个集合, 因为除了\(O\)中的元素之外, 其他集合中的元素也可能已经被覆盖了, 所以\(|O \setminus X_i|\)必然大于等于\(|\{o_i, ..., o_l\}|\), 这就证明了右边的不等式.

这个公式中最左边的一项是\(o_i\)的账单, 所以有\(bill(O) = \sum_{i=1}^l \frac{w(A_i)}{|A_i \setminus X_i|} \le \sum_{i=1}^l \frac{w(O)}{l - i + 1}\). 右边的是一个调和数列, 它的和等于\(w(O) H_l\). 现在我们来看\(w(greedy) = \sum_{j\in \mathcal{U} bill(j)} \leq \sum_{O\in \mathcal{O}}\sum_{j\in O} bill(j)\leq \sum_{O\in \mathcal{O}} H_{|O|w(O)}\leq H_{\Delta} w(\mathcal{O})\).

最小次模覆盖¶

给定一个物品全集\(\mathcal{U}\), 每个物品都有一个权重\(w\), 同时有一个函数\(f\), 用来衡量一个物品子集的价值或者覆盖度. 目标是找到一个权重总和最小的物品子集\(C\), 使其价值\(f(C)\)达到可能的最大值\(f(U)\).

举个例子, 假设我们有\(5\)个关键位置需要监控: \(\{1, 2, 3, 4, 5\}\), 我们有\(3\)个可选的传感器\(a, b, c\)可以购买和部署. \(U=\{a, b, c\}\), 每个传感器都有不同的购买成本\(w(a) = 2, w(b) = 3, w(c) = 4\) , 函数\(f(C)\)计算传感器集合\(C\)能够覆盖多少个不同的位置, 传感器\(a\)能够覆盖\(\{1, 2, 3\}\), 传感器\(b\)能够覆盖\(\{3, 4\}\), 传感器\(c\)能够覆盖\(\{4, 5\}\), 这个\(f\)函数是单调并且次模的, 意味着新增一个传感器, 它能覆盖的新位置的数量会因为已有传感器的存在而减少或者不变, 符合边际效应递减, 目标是找到一个成本最低的传感器组合\(C\), 如\(\{a, c\}\), 使得\(f(C) = f(U) = 5\)且\(w(C)\)最小.

如前面一样, 解决这个问题我们可以用到贪心算法. 从一个空集合\(C\)开始, 在每一步, 计算所有尚未被选中的物品\(j\)的性价比, 这个性价比被定义为物品权重/添加该物品带来的价值增量, 即\(w_j/(f(C+j) - f(C))\). 选择性价比最高(该比值最小)的那个物品\(j\), 并将它加入到集合\(C\)中, 重复此过程, 直到\(C\)的价值\(f(C)\)达到了最大值\(f(U)\).

我们将\(\rho_j(S)\)定义为将一个新的元素\(j\)添加到现有集合\(S\)中年所带来的价值增量或者编辑效应.

定理11.2: 该贪心算法是一个\(1+\ln \Delta\)近似算法.

定理11.3: 如果\(f\)的值域是整数, 那么该贪心算法是一个\(H_{\Delta}\)近似算法, \(\Delta = \max_{j\in \mathcal{U}} \rho_j(\emptyset)\).

我们将最小次模覆盖问题写为一个整数规划模型, 目标是最小化\(\sum_{j\in \mathcal{U}} w_j x_j\), 其中, \(w_j\)表示某个元素的权重, \(x_j\)表示一个二元变量, 表示是否选择该元素. \(S\)是\(\mathcal{U}\)中的任何一个子集, \(f(\mathcal{U})-f(S)\)表示从集合\(S\)到全集\(\mathcal{U}\)所需的额外价值. \(\sum_{j\notin S} \rho_j(S) x_j\)表示我们所选择的那些不在\(S\)中的元素\(j\), 它们各自能够为\(S\)带来的边际效应的总和. 约束条件要求, \(\sum_{j\notin S}\rho_j(S)x_j\)必须大于等于\(f(\mathcal{U}) - f(S)\), 这表示, 我们选择的新元素能够提供的额外价值的总和必须大于等于从\(S\)到\(\mathcal{U}\)还需要的价值. 当子集\(S\)就是我们的终解\(C\)的时候, 这个约束就变成了\(\sum_{j\notin C}\rho_j(C) x^C_j \geq f(\mathcal{U}) - f(C)\), 由于\(x^C_j = 0\), 所以左边就是\(0\), 约束变成了\(0\geq f(\mathcal{u}) - f(C)\), 有\(f(C)\geq f(\mathcal{U})\). 由于\(C\)是\(\mathcal{U}\)的一个子集, 因此我们总是知道\(f(C)\leq f(\mathcal{U})\), 结合这两个不等式, 唯一的结论就是\(f(C) = f(\mathcal{U})\), 这就表明了, 如果一个方案\(x^C\)满足所有整数规划的条件, 那么它必然会使得函数\(f\)的值达到预期的最大值\(f(\mathcal{U})\), 这证明了IP模型的这个方向的正确性, 它不会接受不满足完全覆盖目标的解决方案. 那么, 对于另外一个方向, 假设\(f(\mathcal{U}) = f(C)\), 那么\(f(\mathcal{U}) - f(S) = f(C) - f(S)\). \(f(C) - f(S) \leq \sum_{j\in C\setminus S}\rho_j(S)\)这个是次模函数的核心特性, RHS等于\(\sum_{j\notin S} \rho_j(S)x_j^C\).

可以将这个整数线性规划模型首先进行线性松弛, 然后转为它的对偶形式, 最大化\(\sum_{S\subseteq \mathcal{U}} (f(\mathcal{U}) - f(S)) y_S\), 约束条件是对于每个元素\(j\in \mathcal{U}\), \(\sum_{S\subseteq \mathcal{U}: j\notin S} \rho_j(S) y_S \leq w_j\), 并且\(y_S \geq 0\).

为什么要转化为对偶形式? 因为我们想证明\(w(greedy)\leq \alpha \times w(O)\), 根据强大的对偶定理, 任何一个可行的对欧杰, 它的目标函数值一定小于等于我们的\(w(O)\), 我们可以根据贪心算法的每一步的选择, 构造出一个专属的对偶解\(y_{greedy}\), 并且这个解的值正好等于贪心算法的代价, 即\(Value(y_{greedy}) = w(greedy)\), 但是这个\(y_{greedy}\)还不是一个可行的对偶解, 它不完全满足对偶问题的约束, 恰好超标了\(\alpha\)倍. 那就把\(y_{greedy}\)整体缩小\(\alpha\)倍, 得到一个新的解\(y' = y_{greedy}/\alpha\), 这个\(y'\)就变成一个完全可行的对偶解了, 因为\(y'\)是可行的, 所以根据强对偶理论, 任何一个可行的对偶解的目标函数值, 都是原始问题最优解的一个下界, \(Value(y')\leq w(O)\), \(Value(y')\)是多少呢? 它等于\(Value(y_{greedy})/\alpha\), 也就是\(w(greedy)/\alpha\), 所以\(w(greedy)/\alpha \leq w(O)\), 即\(w(greedy)\leq \alpha\times w(O)\). OK, 我们来看一下完整的流程吧:

设\(C=\{j_1, j_2, ..., j_T\}\), 表示算法在\(T\)步中一次选择了\(T\)个物品, \(S_i\)表示算法在前\(i\)步所选择的物品集合, \(S_0\)是空集. \(\theta_i = w_i/(f(S_i) - f(S_{i-1}))\)是贪心算法在第\(i\)步的选择标准, \(w_i\)是物品\(j_i\)的代价, \(f(S_i) - f(S_{i-1})\)是选择这个物品带来的边际收益, \(\theta_i\)是单位收益的成本, 贪心算法每一步都会选择使这个\(\theta_i\)最小的物品. 这个时候, 我们会构造一个专属的对偶解\(y_{greedy}\), 它是一个向量, 其分量\(y_S\)对应每一个可能的子集\(S\). 其定义见文章, 我们可以计算这个构造出的对偶解的目标函数值\(value(y)\), 发现它正好等于\(\sum w_i\), 即\(w(greedy)\). 但是, 问题是, 这个解并不是一个可行解. 我们需要计算出它超标了多少, 也就是那个因子\(\alpha\), 使得\(\sum \rho_j(S)y_S \leq \alpha \times w_j\)对所有的\(j\)都成立. 经过一系列的复杂推导, 我们得到这个\(\alpha = 1+\ln (\rho_j(\emptyset)/\delta)\).