优化1: 求解顶点覆盖问题和度量斯坦纳树问题的近似算法

franciscochonge · 发表于 2022-3-29 21:11

1. 概述

我们将学习组合优化问题的传统算法. 这些算法是无数应用程序中出现的算法类型, 从数十亿美元的操作到日常的计算任务. 它们可能被航空公司用来规划与定价他们的航班; 可能被大公司用来决定在仓库中囤积什么货物, 在哪个仓库囤积货物; 可能被运输公司用来决定配送卡车的路线; 被奈飞用来决定推荐你什么电影; 被GPS导航器用来规划行车路线等等.
我们要研究的一些问题是NP-hard, 如此我们不太可能设计出精确高效的算法. 对于这类问题, 我们将研究在最坏情况下高效 (worst-case efficient), 但是输出结果可以是次优 (sub-optimal) 的算法. 我们将能够证明最优解 (optimal solution) 和解的代价 (solution cost) 之间的比率的最坏情况界限 (bound). 拥有可证明的输出解质量保证 (provable guarantee) 的次优算法被称作 近似算法 (approximation algorithm).
内容如下:

近似算法的简单例子. 我们将研究顶点覆盖问题 (Vertex Cover), 集合覆盖问题 (Set Cover), 斯坦纳树问题 (Steiner Tree) 和旅行推销员问题 (Travelling salesman problem). 这些算法和他们的分析相对简单, 但是他们引入了不少关键的概念, 包括获得最优解代价上限的重要性.
线性规划 Linear Programming. 线性规划是实数上的优化问题, 我们希望优化一组实变量的线性函数, 服从这些变量的线性不等式系统. 例如:

$\begin{align*} &\text{maximize} \quad x_1 + x_2 + x_3& \\ &\text{subject to:} \\ & 2 x_1 + x2 \leq 2& \\ & x_2 + 2x_3 \leq 1& \end{align*}$
上面线性规划的最优解是, 比如 $x_1 = 0.5, x_2 = 1, x3 = 0$ , 那么我们就有代价为1.5. 一种证明它是最优解的方法是把两个线性约束相加，这告诉我们在每个容许的解中我们都有:

$2 x_1 + 2 x_2 + 2 x_3 \leq 3$
也就是 $x_1 + x_2 + x_3 \leq 1.5$ . 我们能够通过对不等式组求和来验证解的最优性是线性规划的 对偶性 (duality) 的一个特例. 线性规划是基于实数值变量的优化问题, 而组合优化问题是基于 有限个离散解 的问题. 那我们为什么还要研究线性规划问题呢? 这是因为:

线性规划问题可在多项式时间内解出, 在实际中这是很高效的
我们即将研究的所有的组合优化问题都可以被写成线性规划, 只是有一个额外条件: 变量全是 整数值

这导致两个应用:

如果我们对一个问题采用积分线性规划公式, 我们移除完整性要求, 我们将其作为实数上的线性规划以高效地求解, 并且我们足够幸运以至于最优解恰巧有整数值, 那么我们就得到了我们组合优化问题的最优解. 事实上, 对于一些问题, 可以证明每一个输入都会发生这种情况
如果我们对一个问题采用积分线性规划公式, 我们移除完整性要求, 我们将其作为实数上的线性规划以高效地求解, 我们发现解带有小数值, 但是然后我们能够 &#34;四舍五入&#34; 小数值, 使其变成整数, 同时也不会怎么改变解的代价, 那么我们就有了一个高效的 近似算法

接下来的内容有:

通过线性规划的近似算法. 我们将给出各种例子, 可以通过 &#34;四舍五入&#34; 线性规划的小数最优值来设计近似算法
流和匹配问题 (Flows and Matchings) 的精确算法 (exact algorithm). 我们讲研究一些最巧妙并实用的优化算法, 这些算法会找到最优解
线性规划, 流和匹配问题. 我们将展示通过线性规划, 流和匹配问题可以被最优地求解. 理解背后的原理会帮助我们理解线性规划对偶性理论
在线算法 (online algorithm). 在线算法将输入作为流 (stream) 接受, 并且在任意给定时间点, 它都可以仅基于部分已知信息做出决策. 我们将研究两种典型的在线设置: 分页 (paging) 通常是分层存储器中的数据传输, 和投资.

2. 顶点覆盖问题

2.1. 定义

给定一无向图 $\mathcal G = {(V, E)}$ , 顶点覆盖指的是顶点的一个子集  使得对于每条边  都有少一个端点  或者  是  的一个元素. 比如 $V$ 就是一个可行解, 因为它包含了所有边. 而在最小顶点覆盖问题中, 我们的输入是一个图, 目标是找到一个子集包含尽可能少的顶点.
最小顶点覆盖问题与最大独立集问题 (maximum independent set) 非常相关. 在一个图  中, 一个 独立集 指的是顶点的子集 $I \subseteq V$ 使得 $I$ 中 不存在 边  同时有  和  为端点. 最大独立集问题的目标为找到最大可能的独立集.
不难发现, 在图  中, 当且仅当一个集合  的补集 $V - C$ 是一个独立集, 则  为顶点覆盖集. 如此, 从精确算法的角度出发, 这两个问题是等价的: 若  是图  的最优顶点覆盖集, 则 $V -C$ 是图  的最优独立集, 反之亦然. 但是从近似算法的角度出发, 这两个问题并 不等价. 接下来我们将介绍一个线性计算时间的2-approximate算法来求解最小顶点覆盖问题. 顾名思义, 2-approximate算法最差也能找到2倍于最优集合大小的次优集合. 但是对于独立集问题, 却 不存在常数因子 (constant-factor), 多项式时间 (polynomial-time) 的近似算法. 要弄清楚为什么没有矛盾, 以及近似的概念是怎么高度依赖于代价函数的, 我们假设有一个图有  个节点, 其中最优顶点覆盖集的大小为 $0.9n$ , 并且假设我们的算法找到了一个大小为 $n - 1$ 的顶点覆盖集. 然后算法找到一个仅比最优解大 11% 左右的解, 这还不赖. 但是! 从独立集小大的角度来说, 我们的图最优独立集的大小为 $0.1n$ ( $0.9 n$ 的补集), 而我们的算法只找到大小为1的独立集, 这是非常糟糕的.
2.2. 算法

算法很简单:

输入: 图
while ( 存在一条边使得并且 ):
- $C := C ~\cup~ \{u, v\}$
返回

首先初始化我们的集合为空集, 然后当它因为没有覆盖一些边而不能成为一个顶点覆盖集, 我们就添加这条边的两个端点到集合中. 当我们结束 while 循环时, 返回的是解. 为了分析这个近似算法, 我们令 opt 为最小顶点覆盖集的顶点个数, 则我们可以观察到:

若 $M \subseteq E$ 是一个匹配 (matching), 也就是一个没有共同端点的边集, 那么我们必有 opt $\geq |M|$ , 因为内的每条边都必须使用不同的顶点来覆盖
在 while 循环内考虑的边集会形成匹配, 因为若和是在 while 循环内考虑的两条边, 且是先被考虑的那一条, 则当正被考虑的时候, 集合已经包含和 , 因此 $u, v, u', v'$ 都是不同的
若我们令表示在 while 循环考虑的边集, 令 $C_{out}$ 为算法输出的集合, 则我们有 $|C_{out}| = 2 \cdot |M| \leq 2 \cdot \textit{opt}$

正如我们之前所讨论的那样, 这个算法有点不自然. 每次我们找到一条边满足搜索条件, 则两个端点和都会被添加到中, 即使只添加其中一个端点就足以覆盖 . 有点矫枉过正了? 如此, 让我们考虑下面的替代算法:

输入: 图
while ( 存在一条边使得并且 ):
- $C := C ~\cup~ \{u\}$
返回

如果我们的图结构是 &#34;星形&#34;, 那么上面这个算法就有问题了. 很明显最优解是选到中心顶点1, 然而上面的算法可能选择所有的顶点 (除了中心顶点1).

另一种替代算法是贪心算法 (greedy algorithm):

输入: 图
while ( 不是一个顶点覆盖集 ):
- 令为最没有被覆盖的边上的顶点
- $C := C \cup \{ u \}$
返回

上述贪心算法的效果也很差, 对于每个 , 我们可以构建一个图有个顶点, 其中最优解的代价大概在 $n / \text{ln} (n)$ , 但是贪心算法找到的解的代价大概为 $n - n/\text{ln}(n)$ , 所以它不能达到最优解的 常数因子的近似.
3. 度量斯坦纳树问题

在斯坦纳树问题 (Steiner Tree problem) 中, 给定必要点集 (a set of required points) $R$ 和可选点集 (a set of optional points) $S$ , 以及距离函数 $d: (R \cup S) \times (R \cup S) \to \mathbb R_{\geq 0}$ . 距离函数就是我们所说的度量 (metric), 对于每两点 $x, y$ 我们都有 $d(x, y) = d(y, x)$ , 并且对于每三个点 $x, y, z$ 我们都有三角不等式:

$d(x,y) \leq d(x, z) + d(z, y)$
我们的目标是找到覆盖 (span) 所有必要点, 并有可能使用一些可选点的树 $\mathcal T = (V, E)$ , 也就是 $R \subseteq V \subseteq \{R \cup S\}$ , 使得树的总长度 $\sum_{(x, y) \in E} d(x, y)$ 最小.
该问题与最小生成树 (minimum spanning tree) 问题非常相似, 最小生成树问题有精确算法, 可以多项式 (事实上接近线性) 时间内跑出结果. 在最小生成树问题中, 已知一张加权图, 我们可以将其视为一点集和一距离函数 (可能不满足三角不等式), 并且我们想要找到包含所有顶点的最小总距离的树. 不同之处在于, 最小斯坦纳树问题只需要覆盖所有顶点的子集, 而其他的顶点旨在对构建更短总距离的树有帮助时, 才被包含进解中.
我们考虑如下近似算法: 在必要点集上运行一最小生成树算法, 也就是找到最佳可能的, 不使用可选点的树. 接下来的课程中我们将证明这个算法可以取得2近似的因子.
<hr/>原文链接

		自动登录	找回密码
密码			立即注册

优化1: 求解顶点覆盖问题和度量斯坦纳树问题的近似算法

本帖子中包含更多资源