最大次模覆盖

什么是最大覆盖问题¶

给定一个全集\(\mathcal{U}\)和一个由\(\mathcal{U}\)的\(m\)个子集构成的集合\(\mathcal{S} = \{S_1, ..., S_m\}\). 从\(\mathcal{S}\)中挑选出\(k\)个子集, 要求这\(k\)个子集的并集中所包含的元素数量要达到最大. 这是一个NP-hard问题, 意味着对于大规模的数据, 很难在合理的时间内找到最优解. 因此, 通常会为他设计一个近似算法来寻找一个接近最优的解.

近似算法-以贪心算法为例¶

近似算法是一种用于解决优化问题的方法, 它能在多项式时间内运行完成, 并返回一个结果. 这个结果虽然不一定是最优解, 但是能保证其成本和最优解的差距在某个因子\(\rho\)之内.

贪心算法就是一种常见的近似算法, 该算法非常直接, 是一种短视的策略. 首先, 初始化一个空集\(\mathcal{C}\)作为解, 重复\(k\)次以下的操作: 从所有可选子集\(\mathcal{S}\)中, 挑选出一个能够覆盖最多新元素的子集, 将这个选出的子集加入到\(\mathcal{C}\)中, 返回集合\(\mathcal{C}\).

总体上来说, 贪心算法返回的不是最优解. 假设\(k=2\), 即挑选\(2\)个子集. 假设第一步选择了\(S_3\), 那么之后一个只能选\(S_1\)或者\(S_2\)(无论选哪个, 新增元素的数量都是\(0.5\)l). 但是最优解的选择应该是\(S_1\)和\(S_2\), 这样可以覆盖所有的元素. 贪心算法因为其短视, 导致无法找到全局最优解.

定理10.1: 对于最大覆盖问题, 贪心算法是一个\(1-1/e\)近似算法, 这意味着, 贪心算法找到的解的大小, 至少是最优解大小的\(1-1/e\)倍.

证明: 设\(OPT\)是最优解能覆盖的元素总数. \(A_1\), \(A_2\), ...是贪心算法按照顺序选出的\(k\)个子集. \(X_1\), \(X_2\), ...是贪心算法选了\(i\)个子集后, 总共覆盖的元素的集合, \(|X_1|\), \(|X_2|\), ... 对应集合中元素的数量. 证明分为\(k\)步, 逐步分析每一步的贪心算法能带来多大的收益:

第一步: 贪心算法选择第一个子集\(A_1\)是所有子集中最大的, 它的元素数量\(|X_1|\)必然大于等于最优解中\(k\)个子集的平均大小, 所以可以推导出: \(|X_1|\geq OPT/k\), 第二步, 贪心算法选择\(A_2\)是为了覆盖更多新的元素, 证明的关键在于, 这次新增的元素数量\(|A_2/\ X_1|\)至少是最优解中尚未被覆盖部分的\(1/k\), 可以表达为新增的数量\(\geq (OPT-|X_1|)/k\). 于是, 两步之后覆盖的总数\(|X_2|\)就满足\(|X_2|=|X_1|+\)新增数量\(\geq |X_1|+(OPT - |X_1|)/k\). 这个逻辑可以一直往下推, 在每一步\(i\)中, 贪心算法都能覆盖掉剩余最有价值的至少\(1/k\), 经过\(k\)步后, 这种每次至少剩下部分的\(1/k\)的过程, 最终能保证覆盖的总数\(|X_k|\)满足: \(|X_k|\geq OPT \times (1-(1-1/k)^k)\), 数学上可以证明, 当\(k\)足够大的时候, \((1-1/k)^k\)这个值约等于\(1/e\), 因此, 贪心算法的解的大小至少是最优解的\(1-1/e\)倍.

最大次模覆盖问题¶

上面提到了最大覆盖问题, 这里我们要讲一下最大次模覆盖问题. 最大次模覆盖问题和最大覆盖问题类似, 但是有一个重要区别, 就是每个元素都有一个权重或者价值. 我们要从一个大集合\(\mathcal{U}\)中, 挑选出最多\(k\)个元素组成一个子集\(\mathcal{C}\), 目标是让这个子集的价值\(f(\mathcal{C})\)最高.

这个价值函数有三个关键的特性:

第一个是单调非递减, 往集合里面添加新的元素, 总价值不会降低;
第二个是次模性, 这是最重要的特性, 可以理解为边际效应递减, 即, 向一个小集合里面增加一个新元素带来的价值提升, 要大于等于向一个大集合里面增加同一个元素带来的价值提升.
归一化: 一个空集合的价值为0.

当一个函数\(f\)同时满足这三个条件时, 求其最大值的问题就叫做"最大次模覆盖问题". 这类问题在很多领域都有应用, 比如影响力最大化, 传感器布局等.

贪心算法¶

解决这种问题的一个常用的方法是贪心算法, 每次迭代都选择那个能够使得价值\(f\)增长最大的元素, 直到选出\(k\)个元素为止.

定理10.2: 对于最大次模覆盖问题, 贪心算法是一个\(1-1/e\)近似算法.

证明: 定义\(OPT\)为最优解的价值, \(o_1, ..., o_k\)为最优解包含的\(k\)个元素. \(a_1, a_2, ..., a_k\)是贪心算法选出的\(k\)个元素.

我们首先来分析第一步, 贪心算法的第一步是先择单个价值最高的元素. 因此\(a_1\)的价值\(f(a_1)\)必然大于等于任何其他单个元素的值, 包括最优解里面的任何一个元素\(o_j\), \(f(a_1)\geq f(o_j)\). 有\(f(a_i)\geq \max_j (f(o_j)-f(\emptyset))\geq (\sum_j f(o_j)-f(\emptyset))/k\), 然后, 我们要利用边际递减效应, 这个值\(\geq (\sum_j (f(\{o_1, ..., o_j\})-f(\{o_1, ..., o_{j-1}\})))/k\), 因为后者是给一个已经包含很多元素的集合增加\(o_j\)带来的价值, 前者是给空集增加\(o_j\)带来的价值. 对后者进行化简, 中间项抵消之后, 会\(=(f(\{o_1, ..., o_k\}) - f(\emptyset))/k\), 分子就是\(OPT\), 所以得到\(=OPT/k\). 所以, 我们得到\(f(a_1)\geq OPT/k\).

对于第二个元素, 我们有\(f(\{a_2, a_1\})-f(a_1)\geq f(\{o_j, a_1\})-f(a_1)\). 接下来的推导和上一段非常的相似, 最终得到\(f(\{a_1, a_2\})\geq (OPT-f(a_1))/k\).

接下来, 根据一系列的代数变换, 将上一步的结论\(f(a_1)\geq OPT/k\)带入, 可以得到\(f(\{a_1, a_2\})\)的一个更强的下界, 重要的是, 这个逻辑可以被数学归纳法推广到任意一步\(i\), \(f(\{a_1, ..., a_i\})\)的价值至少是\((OPT/k)\)乘以一个等比数列的和\((1 + (k-1)/k + ... + ((k-1)/k)^{i-1})\). 证毕.

应用¶

带容量的传感器覆盖问题¶

目标是在一系列指定地点部署传感器来收集数据. 传感器只能收集与子集距离在\(R\)内的地点的数据. 每个传感器最多只能记录\(l\)个地点的数据. 问题是, 如何选择\(k\)个位置放置传感器, 并为它们分配检测任务, 才能使得被检测的地点总数量多.

这个问题可以被建模为数学上的子模覆盖问题, \(\mathcal{U}\)代表所有可以安放传感器的备选位置的集合. \(f(S)\)是一个函数, 当你选择了一组具体的安放位置\(S\)的时候(\(S\)是\(\mathcal{U}\)的一个子集), 这个函数会计算出, 在满足传感器容量和距离限制的条件下, 这组传感器最多能检测到的地点数量. 文章指出, 对于这一类问题, 一个叫做GREDDY-SUBMODULAR的贪心算法可以给出一个近似最优解. 最后的引理10.1确认了目标函数\(f\)满足贪心算法所需要的性质(单调非减, 子模性), 因此该算法是有效的.

那么, 我们如何计算\(f(S)\)呢? 也就是当你选定一组传感器位置\(S\)之后, 如何找出它们最多能检测的地点数量. 文章将这个问题巧妙地转化为了一个经典的计算机科学问题: 最大流问题. 起点\(s\)代表总的检测能力的源头, 第一层节点\(S\)代表你选择放置的传感器, 从起点\(s\)到每个传感器的管道容量为\(l\), 这代表每个传感器最多能监测\(l\)个地点. 第二层节点代表所有等待被监测的地点, 只有当某个地点\(y\)在传感器\(x\)的监测距离\(R\)以内的时候, 才会在它们之间连接一条管道, 容量为\(1\), 这代表每一个传感器一次只能去监测一个地点. 终点\(t\)代表成功被监测的地点汇集处, 从每个待监测地点到终点\(t\)的管道容量为1, 这样保证了就算一个地点可以被多个传感器监测, 它最终也只被记作1个被成功监测的地点. 在这个网络中, 从起点\(s\)流向终点\(t\)的最大总流量, 就等于\(f(S)\)的值.

影响力最大化问题¶

简单来说, 研究的是在一个社交网络中, 如何通过最开始激活一小部分人, 来最大化一个趋势或者信息(比如一个新的产品, 一个新的想法)的最终传播范围.

这个过程可以通过一个有向图来建模, 节点代表网络中的人, 边代表任何人之间的关系和影响方向, 每个节点可以是激活或者未激活的状态. 一开始, 所有的节点都未激活, 当一个节点被激活后, 它会尝试去影响它的邻居, 每次影响都有一定成功的概率, 如果成功, 邻居节点也会被激活, 节点一旦被激活, 就会永远保持激活的状态, 新激活的节点会继续尝试影响它的邻居, 形成一个级联的效应.

核心问题就是: 如何要选择\(K\)个初始节点去激活, 才能最大化最终被激活的节点数量. 整个社交网络被模型化为一个有向图\(G\), 其中\(V\)是所有人的集合, \(E\)是它们之间的关系的集合. 有向意味着影响是单向的, 比如A关注了B, A会受B影响, 但是不一定反过来. 每条边都有一个0到1之间的概率\(p\), 表示了一个节点试图影响另一个节点的时候, 影响能够成功传递的概率, 例如, \(p(u, v)\)就是\(u\)成功激活了\(v\)的概率. 节点只有两种状态, 激活或者未激活, 一旦一个节点被激活, 它将永远保持激活状态, 不会再变回去. 当一个节点\(u\)变得激活的时候, 它会尝试去影响它的所有出邻居, 这个影响值对当前还未激活的邻居\(v\)有效, 邻居\(v\)是否被激活, 取决于一个概率事件, 它有\(p_{u, v}\)的概率被激活.

设\(S\)为最初选择激活的种子集, \(\sigma(S)\)为最终被激活的节点的期望数量, 这里的期望很重要, 因为传播的过程是带概率的, 每次结果可能不同, \(\sigma(S)\)是多次实验后的平均结果. 问题的目标是, 找到一个大小不超过\(k\)的节点子集\(S\), 使得\(\sigma(S)\)最大化. 用公式表达就是\(\max _{S \subseteq V} \sigma(S)\)并且\(|S|\leq k\).

可以被证明\(\sigma\)是一个单调非递减的次模函数, 因此可以使用贪心算法来近似求解这个问题. 归结为引理10.2.