近似算法

对于一个问题，有时候我们很难高效地求出问题的精确解，却能求出在一定偏差范围内的近似解。以图上的最大独立集问题为例，假设当问题的答案为$K$时，我们的算法总能找到一个$\geq 0.5K$的解，那么就称这个算法为一个最大独立集问题的$0.5$-近似算法。很多NP-hard问题没有多项式算法，但可以有多项式近似算法。

最小点覆盖的2-近似算法

图的一个点覆盖是一个点集，使得每条边至少有一个端点在这个点集里。最小点覆盖问题是NP-hard问题。

我们任意的一条条选边，同时保证这些边构成一个匹配（已经被选的边两两没有公共顶点），直到没有边能被加进来，这时候我们就得到了一个“极大匹配”。注意“极大”不一定是“最大”。假设这个极大匹配的边数为$M$。

我们发现“极大匹配”中所有的顶点（$2M$个）一定能构成一个点覆盖，因为如果存在一条边没有被覆盖，那么这条边的两个顶点都不在极大匹配中，那么根据匹配的定义，这条边一定可以被加到极大匹配里，这就与“极大”矛盾了。

同时我们发现，最小点覆盖至少要有$M$个点。我们要覆盖所有的边，至少要覆盖这$M$条边，因此每条边至少有一个端点要被选进最小点覆盖。而极大匹配中的边是两两独立的，选某条边的一个端点只能覆盖这$M$条中的一条。因此每条边至少要选一个点，最小点覆盖至少要有$M$个点。

因此答案$K \geq M$，我们已经找到了一个$2M$的答案。$\dfrac{2M}{K} \leq 2$，因此“找极大匹配”就是一个2-近似算法。

$\dfrac{2M}{K} \leq 2$中的等号会不会其实取不到呢？即我们能否通过“更好的分析”来发现这实际上是一个更好的近似（比如1.9）？答案是否定的，我们只需要找到一个Tight Example：构造这样一张图，它是$n$条两两独立的边，最小点覆盖应当是$n$，我们的算法会给出$2n$，于是我们说明了等号是会被取到的。那么我们只能说这是个2-近似算法。

考虑另外一种贪心的做法，每次选出度数最大的一个点，然后把与它相连的边全删掉。这似乎也是一种不错的近似算法，但事实证明，可以构造出一个反例使得它的近似系数达到无穷大。

Max-3SAT

我们将3SAT问题“每一项都为true（CNF输出true）”的判定问题改为“最多能使多少项为true”的优化问题，就得到了Max-3SAT问题。这也是NP-hard问题。

首先来考虑这样一个平凡的随机算法——以0.5的概率随机给每个变量赋值。我们来计算这样得到的答案的期望。根据期望的线性性，我们只需计算每项为true的概率。由于每项内部的变量是用$\vee$连接的，因此false的概率只有1/8，所以true的概率是7/8。假设总共有$m$项，我们的随机算法给出的答案期望就是$\dfrac{7}{8}m$。

设总共有多少项为true的随机变量为$Y$。那么成立$E(Y)=\dfrac{1}{2}E(Y|x_1=1)+\dfrac{1}{2}E(Y|x_1=0)$。于是一定有$E(Y|x_1=1) \geq E(Y)$或$E(Y|x_1=0)\geq E(Y)$。我们已经知道算期望的算法是平凡的了（只需按照已知条件算出每一项的期望相加），我们令$x_1=v_1$从而使得$E(Y|x_1=v_1) \geq E(Y)$的那个值。接下来，成立$E(Y|x_1=v_1)=\dfrac{1}{2}E(Y|x_1=v_1,x_2=0)+\dfrac{1}{2}E(Y|x_1=v_1,x_2=1)$，依次类推我们令$x_2=v_2$从而有$E(Y|x_1=v_1,x_2=v_2) \geq E(Y|x_1=v_1) \geq E(Y)$。不断迭代，最终我们得到$E(Y|x_1=v_1,\cdots,x_n=v_n)\geq E(Y)=\dfrac{7}{8}m$，而左侧已经不是一个随机变量了，它是一个确定的赋值。综上，我们已经得到了一个$\dfrac{7}{8}$-近似算法。

Max-Cut

把图上的点集分成两组，把所有“一端在一个点集另一端在另一个点集”的边收集在一起就称为一个Cut（割）。

Max-Cut是NP-hard问题。

考虑这样一个基于贪心的近似算法。首先把点集任意分成$A,B$两组。此时如果能找到一个点，把它放到另一边会产生更大的Cut，那么就把它放另一边。不断重复上述过程，直到不能找到能产生更大Cut的点。

这个过程是多项式复杂度的，由于Max-Cut不超过总边数，每次更新Max-Cut至少加一，因此不可能更新超过总边数次；每次更新最多找总点数次，判断每个点不超过总边数次复杂度。总复杂度不超过$O(|V||E|^2)$。

对于终态我们观察到，对于$A$中的每个点，假设它有$a$条边连向点集$A$，有$b$条边连向点集$B$。那么一定有$a \leq b$。如果$a>b$，那么把它放到$B$中一定能产生更大的Max-Cut。$B$中的点同理。我们可以这样统计Max-Cut——考虑每个点对Max-Cut的贡献，那么每条边会恰好被算两次。根据我们得到的不等关系，我们的算法得到的答案至少$\geq \dfrac{1}{2}\sum\limits_{u \in V}\dfrac{1}{2}\deg(u)$。而根据握手定理，$\sum\limits_{u \in V}\deg(u)=2|E|$，因此我们得到了一个大小至少为$\dfrac{|E|}{2}$的Cut。

而显然Max-Cut$\leq |E|$。因此这至少是一个0.5-近似算法。我们可以给出一个Tight Example证明这就是一个0.5-近似算法。

这并不是最优的多项式近似算法，对于Max-Cut问题，最优的多项式近似算法可以做到0.878。

$k$-centers

定义一个点$u$到无向图上一个点集$S$的距离$d(u,S)=\min\limits_{v \in S}\{d(u,v)\}$，这个$v$就是$u$对应的center。问怎么选这个$S$才能让$\max\limits_{u \in V}\{d(u,S)\}$最小。显然$S$中点越多答案就可以做到越小，k-centers规定$S$中只能有$k$个点，要求最小化答案。

考虑这样一个贪心的算法：首先任选一个点加入$S$。然后找到使得$d(u,S)$最大的那个点$u$加进$S$里。直到选完$k$个。

我们来证明这是一个近似算法。我们找到的这个点集记为$A$，标准答案的点集记为$O$。并且设我们的答案是$ALG$，标准答案是$OPT$。设$O$中的第$i$个点为$o_i$，所有以$o_i$作为center的点组成点集$X_i$。$X_1$到$X_k$就构成了对$V$的一个划分。

如果$A$与每个$X_i$都有交集，那么根据鸽巢原理每个$X_i$里面恰好有一个$A$中的点，记为$a_i$。$X_i$里的每个点$v$一定满足$d(o_i,v) \leq OPT$，因此也有$d(o_i,a_i) \leq OPT$。相加得到$d(a_i,v)\leq d(a_i,o_i)+d(o_i,v) \leq 2OPT$。也就是说，$\forall v\in X_i,d(a_i,v)\leq 2OPT$。因此$\forall v\in X_i,d(v,A)\leq d(v,a_i)\leq 2OPT$。所以令$i$取遍$1$到$k$，得到$\forall u\in V,d(u,A)\leq 2OPT$，也即$\max\limits_{u\in V}d(u,A)=ALG\leq 2OPT$。

如果存在一个$X_i$与$A$没有交集，那么根据鸽巢原理会有一个$X_j$里有$a_p,a_q$。根据我们的贪心算法，假设$a_q$是后被选进来的那个点，这意味着$d(a_p,a_q) \geq ALG$。而$d(a_p,a_q) \leq d(a_p,o_j)+d(a_q,o_j) \leq 2OPT$，因此也有$ALG \leq 2OPT$。

综上，$\dfrac{ALG}{OPT} \leq 2$，这是一个2-近似算法。一个Tight Example就是一条三个点的链，如果第一步选了边上的点那么就得到答案是2，正确答案是1。

不可近似性

我们如何证明不存在一个更优的多项式时间复杂度的近似算法呢？我们用反证法，假设这样的算法存在，然后证明它可以用来解决NP-hard问题。这就会导致P=NP，就是我们认定的“矛盾”。

Dominating Set

如果能选出图上的一个点集$S$，使得所有不在$S$中的点都至少有一个相邻点在$S$中，就称$S$为一个Dominating Set。

我们证明点覆盖判定问题可以归约为Dominating Set判定问题。对于$G$，我们可以这样构造一个$G'$：将$G$中的每条边拆成两条边，中间加上一个新的点；然后让所有旧点之间两两连边。假设$G$有一个$k$个点的点覆盖，那么在$G'$中选同样的点一定能构成一个Dominating Set。如果$G’$里有一个$k$个点的Dominating Set，假设它包含了新点，由于新点只连接两个旧点且不连别的新点，所以每个被选的新点如果被换成相邻的旧点依然能构成一个Dominating Set。所以我们在$G'$中一定有一个至多$k$个点（向下兼容）的Dominating Set，相应的这一定构成$G$中的一个点覆盖。

因此Dominating Set问题是NP-hard问题。

k-centers的$(2-\varepsilon)$-不可近似性

如果$G$有一个$k$个点的Dominating Set，那么k-centers的答案就是1。（不考虑0）。如果没有，那么答案至少为2。

我们知道k-centers的2-近似算法复杂度是多项式的。如果我们能有一个多项式复杂度的$(2-\varepsilon)$-近似算法，如果$ALG=1$，那么$OPT=1$，我们能判定$G$有一个$k$个点的Dominating Set；如果$ALG \geq 2$，那么$OPT \geq \dfrac{ALG}{2-\varepsilon} > \dfrac{ALG}{2} \geq 1$，那么$OPT \geq 2$，说明$G$不存在$k$个点的Dominating Set。于是，我们竟然可以在多项式时间复杂度内判定Dominating Set了！这将会导致P=NP，我们相信这是不可能的。