demonstrate 的 blog

手头这本近似算法算是用来了解一些常见的算法问题以及对应问题难度的工具。大致计划是 3 天更新一篇，约一天一个问题。近似算法一般都是研究一些 NP-hard 的问题（对非 NP-hard 的也有研究，如近似最近邻等），某些 NP-hard 问题可以被任意程度的近似，而有些却不可以，通过这些研究我们就可以将 NP-hard 问题进一步细分。

我们先简单的回顾一下 complexity 的分类。P 指 deterministic polynomial-time solvable，我们能找到一个确定性的多项式时间的 Turing machine 对问题进行求解，而 NP 是指 non-deterministic polynomial-time solvable，即这个问题满足是多项式时间可验证，同时能通过不确定性的 Turing machine 在多项式时间可解。co-NP 是指一个问题的 complement 是 NP。NP-complete（NPC）是指最难的一类 NP 问题，亦即如果这类问题可以求解，任意 NP 问题都可以通过多项式时间的规约转换成该问题求解（不比任意 NP 问题容易）。NPC 最早是证明了任意 decision problem 都可以（多项式时间）规约到 3-SAT，且 3-SAT 是 NP 问题，从而 3-SAT 是 NPC。至此人们只需要证明任意一个 decision problem 如果是 NP 且不比 3-SAT 容易（可以将 3-SAT 多项式时间规约到该问题），就能说明这个问题是 NPC。而 NP-hard 是指比不比最难的 NP 问题容易的问题（因此 NP-hard 包含更难的问题），也就是说如果以 NP-hard 问题作为 oracle，任意 NP 问题都是多项式时间可解（因此只需要说明一个 NPC 问题是多项式时间可解即可）。

P ?= NP

近似算法所谓近似，往往是针对 optimization problem 来说的（而不是经典的 decision problem），一个 optimization problem 为 NP-hard 当且仅当确定一个可行解是否为最优解这个 decision problem 是 NP-hard。这样似乎有点矛盾的是，要确定近似算法的“近似程度”我们必须知道最优解是什么，但是找到最优解却很难。为了解决这个问题，我们常为这些（minimization）问题引入 lower bound。借助 lower bound 我们就可以估计出来近似的程度，并讨论是否能够获得更好地近似。

沿着这个思路，我们以 set cover 这个问题为例看看大致的研究过程是如何的。

Vertex cover problem 给定一个无向图 ，定义在每个顶点上的 cost function 为 ，要求给出顶点集的子集 ，满足 ，即任意一条边存在至少一个顶点在集合 中，且 。

比较常见的选择是 ，这时也称为 cardinality set cover problem。对这个特例，我们可以借助所谓 maximum matching 获得 lower bound。

Maximum matching problem 给定一个无向图 ，寻找一个边集的子集 ，且 ，即任意该子集中的两条边都不会有公共端点，要求这样的 元素个数最多。

这样获得的边子集实际上表述了顶点之间的两两对应关系（也就是所谓的 matching）。比较容易获得 maximum matching 的算法自然是 Edmond’s maximum matching 算法。这样获得的子集中边的个数实际上就为 set cover problem 提供了一个下界：因为 vertex cover 选择的顶点必然出现在 maximum match 的边集的某条边上，这样边数不多于 vertex cover 的顶点数。

利用 maximum matching 我们能获得 approximation factor 为 2 的算法：将 maximum matching 获得边集里面所有的顶点全部加入。因为这是 maximum matching，不论哪条边（不在 matching 里面的）都与 matching 给的某条边有公共顶点。近似程度为 2 是指这个算法最坏情况下给出的顶点数是最优解的两倍。事实上，maximum matching 与 vertex cover 是对偶问题。

Set cover problem 给定论域 大小为 ，上有集族 是 的子集形成的集合，定义了一个代价函数 ，寻找 的子集，使得该子集包含的集合的并为 ，且对应的代价和最低：。

求解这个问题可以使用 greedy 策略，每次将平均代价最高的集合从 选择出来：

1. 初始化 ；
2. 如果 ，则继续，否则跳到第 6 步；
3. 为每个 剩余的子集 计算平均代价 ，
4. 选择平均代价最低的子集 加入 $\mathcal{T}$，并 ；
5. 返回 2；
6. 输出结果

这个算法获得的解与最优解相差多少呢？可以证明是最优解的 倍。事实上，每次选择的时候付出的价格可以被最优值 的 bound。

另一种是利用所谓 frequency 来做的。定义论域中元素出现在某些集合中的次数为 frequency，记所有元素中最频繁出现的次数为 。vertex set 可认为是 的问题，因为一条边对应 2 个顶点，这样对应的论域是边集，而对应每个 是每个顶点关联的所有边组成的集合。还有一类策略获得的近似算法与 f 有关系，我们这里仅用 vertex cover 作为例子，其策略称为 layering，即将定义在顶点（）上的权值函数分解成几层（几个权值函数的和），然后对每层满足条件（所谓 degree weighted，即权值函数正比于 degree 或者 中元素个数）的权值函数，我们都有策略可以获得近似覆盖的界。

可以方便的证明，如果是一个 degree weighted 权值函数，就算我们选择所有的子集对应的 cost 不会超过最优值的 倍。这样，我们可以将给定的权值函数分解：

• 去掉空集；
• 在剩余的集合里面选择 最低的（记为 ）；
• 从现在权值函数里面去掉

这样直到所有的被取完。这样相当于每层对应都是 degree weighted 且常数为 的权值函数，这样我们整体的 cost 就能被 bound 了。

作为 set cover 的应用，我们来看 shortest superstring 问题。

shortest superstring 给定 个字符串（简单起见，两两互不为子串），要求给出一个最短的字符串，这 个字符串都是它的子串。

很明显，论域可以认为是这 个latex 字符串组成的集合 ，而子集族是从 或者 和 拼接字符串 选择字符串 形成的集合 。这样就可以利用前面的算法了。

——————
Arise, walk through the land in the length of it and in the breadth of it; for I will give it to you.