登高必自卑，自视太高不能达到成功，因而成功者必须培养泰然心态，凡事专注，这才是成功的要点。

考虑这样一个 Set cover 问题：

给定一个全集$U$ 和一系列它的子集$S_1,S_2,...,S_m\subseteq U$，每一个子集都有一个权重$C(S_i)$。
我们希望求一个权重最小的 cover：即所有满足$\bigcup_{S\in \mathcal{T}}S=U$ 的集合$\mathcal{T}\subseteq\{S_1,...,S_m\}$ 中，$\sum_{S\in\mathcal{T}} C(S)$ 最小的那个。
我们一般默认权重是非负的$C(S)\geq 0$。

# 贪心做法

考虑一个简单的贪心做法。
我们选择 “能覆盖范围和权重比值最大的集合”：

$$\begin{aligned} & T_1=\argmax_{S\in \{ S_1,...,S_m \}}\frac{|S|}{C(S)},\\ & T_2=\argmax_{S\in \{ S_1,...,S_m \}}\frac{|S\setminus T_1|}{C(S)},\\ & T_3=\argmax_{S\in \{ S_1,...,S_m \}}\frac{|S\setminus (T_1\cup T_2)|}{C(S)},\\ & ......\\ & T_m=\argmax_{S\in \{S_1,...,S_m\}} \frac{|S\setminus (T_1\cup...\cup T_{m-1})|}{C(S)}. \end{aligned}$$

这样我们找出了一个集合$\{T_1,...,T_m\}$ 作为答案。假如说原问题最优解的集合是$\mathcal{V}=\{V_1,...,V_t\}$，那么根据贪心算法的过程，我们知道：对于任意$1\leq i\leq m$，

$$\begin{aligned} & \frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}&\geq \frac{|V_1\setminus(T_1\cup...\cup T_{i-1})|}{C(V_1)}\\ & \frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}&\geq \frac{|V_2\setminus(T_1\cup...\cup T_{i-1})|}{C(V_2)}\\ & \frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}&\geq \frac{|V_3\setminus(T_1\cup...\cup T_{i-1})|}{C(V_3)}\\ & ......\\ & \frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}&\geq \frac{|V_t\setminus(T_1\cup...\cup T_{i-1})|}{C(V_t)}. \end{aligned}$$

根据不等式：

$$\max\left \{ \frac{a_1}{b_1},...,\frac{a_l}{b_l}\right \}\geq\frac{a_1+...+a_l}{b_1+...+b_l},$$

我们可以得到

$$\frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}\geq \frac{\sum_{j=1}^t |V_j\setminus\{T_1\cup...\cup T_{i-1}\}|}{C(V_1)+...+C(V_t)}.$$

注意到因为$\{V_1,...,V_t\}$ 是个 cover，所以

$$\sum_{j=1}^t |V_j\setminus\{T_1\cup...\cup T_{i-1}\}|\geq |U\setminus \{T_1\cup...\cup T_{i-1}\}|=|U|-|T_1\cup...\cup T_{i-1}|.$$

我们知道最优解$OPT=C(V_1)+...+C(V_t)$，再结合上述分析，所以有

$$\begin{aligned} \forall 1\leq i\leq m,\ \frac{|T_i\setminus(T_1\cup...\cup T_{i-1})|}{C(T_i)}\geq\frac{|U|-|T_1\cup...\cup T_{i-1}|}{OPT}\\ \end{aligned}$$

因此我们知道

$$\sum_{i=1}^m C(T_i)\leq OPT\cdot \left (\frac{|T_1|}{|U|}+\frac{|T_2\setminus T_1|}{|U|-|T_1|}+\frac{|T_3\setminus (T_1\cup T_2)|}{|U|-|T_1\cup T_2|}+...+\frac{|T_m\setminus(T_1\cup...\cup T_{m-1})|}{|U|-|T_1\cup T_2\cup...\cup T_{m-1}|}\right ).$$

实际上仔细观察可以知道右侧式子其实是个调和级数：

\begin{aligned} & \frac{|T_1|}{|U|}=\underbrace{\frac{1}{|U|}+...+\frac{1}{|U|}}_{|T_1|\mbox{个}}\leq \frac{1}{|U|}+\frac{1}{|U|-1}+...+\frac{1}{|U|-|T_1|+1},\\ & \frac{|T_2\setminus T_1|}{|U|-|T_1|}\leq \frac{1}{|U|-|T_1|}+\frac{1}{|U|-|T_1|-1}+...+\frac{1}{|U|-|T_1|-|T_2\setminus T_1|+1},\\ \end{aligned}

其中$|U|-|T_1|-|T_2\setminus T_1|=|U|-|T_1\cup T_2|$。以此类推，我们可以得到

$$\sum_{i=1}^m C(T_i)\leq OPT\cdot \sum_{j=1}^{|U|}\frac{1}{j}=O(\log |U|).$$

因此实际上这个贪心算法得到的解之多是$O(\log |U|)$ 倍的近似解。

# Vertex Cover 的 layering technique

我们考虑如下 Vertex Cover 问题：

给定一个无向图$G=(V,E)$，每个点$u\in V$ 有一个权重$C(u)$。
$G$ 的一个 cover 是$V$ 的一个子集$T\subseteq V$ 使得每条边$e\in E$ 都至少有一个与其相关联的点在$T$ 中。
我们希望找到权重和最小的 cover。

很显然 Vertex Cover 可以归约到 Set Cover，我们只需要令$U=E$，然后每个点是一个子集：

$$S_u=\{e\in E:u\text{是}e\text{的一个端点}\}\subseteq U.$$

这样 Set Cover 的最优解就是 Vertex Cover 的最优解。

我们考虑另一个近似算法。首先定义一种 Degree-weighted graph:

一个图$(V,E)$ 被称为是 degree-weighted 的，如果存在一个常数$C$ 使得：

$$\forall u\in V,\ \frac{C(u)}{deg(u)}=C.$$

我们首先知道一个引理：

证明：这很简单，我们可以证明一个 degree-weighted 的图的最优 vertex cover $\geq$ 所有点权重和 / 2。
我们可以想象，每个点的权重都被分配到和它相关联的边上，如下图：

那么很显然，一个 vertex cover 需要盖住所有边，所以最优 vertex cover 的权重至少$\geq$ 边数 $\times C$，也就是所有点权和的一半。
$\square$

因此一个算法就是，我们可以把一个图拆成一个 degree weighted 的图，和一个剩余图的和。
我们只需要找出一个图中，$\frac{C(u)}{deg(u)}$ 最小的那个顶点$u$。然后呢，我们可以把图拆成两个图的和：

在上图中，最小的顶点$A$ 对应的比值就是$1/5$。不难发现，这样拆分后，剩余图$G_2$ 中$A$ 的权重就是 0 了，而$G_1$ 是一个 degree-weighted 的图。

根据前面的引理，$G_1$ 任意的 vertex cover 都是 2 - 近似的，因此我们只需要考虑$G_2$ 的 vertex cover 选法。
很显然，$G_2$ 中我们可以直接选择权重为 0 的那个点，这样的话$G_2$ 就会被化简：把和$A$ 相关联的边都删掉。

然后重复上述过程，最后就可以得到一个 vertex cover 选法，而且相对于最优解是 2 - 近似的。

# Linear Programming 和 Integer Programming 的近似方法

我们首先回忆一下 linear programming 的 duality 和 slackness 的一些结论。
考虑下面两个 linear programming 问题，左侧的被称为 primary problem，右侧是它的 dual problem。其中，$b,y$ 是$m$ 维向量，$c,x$ 是$n$ 维向量，$A$ 是$m\times n$ 维矩阵。

$$\begin{aligned} &\min && c^Tx\\ & s.t. && Ax\geq b\\ & && x\geq 0 \end{aligned}\qquad\qquad \begin{aligned} &\max && b^Ty\\ & s.t. && A^Ty\leq c\\ & && y\geq 0 \end{aligned}$$

我们知道，这两个问题的最优解是相等的。而且有两个重要的结论：

而且互补松弛性还有一个有用的结论：

证明：注意到

$$\begin{aligned} & \sum_{i=1}^m\sum_{j=1}^n A_{i,j}x_jy_i=\sum_{i=1}^m\left (\sum_{j=1}^n A_{i,j}x_j\right )y_i\leq \beta\sum_{i=1}^m b_iy_i,\\ & \sum_{i=1}^m\sum_{j=1}^n A_{i,j}x_jy_i=\sum_{j=1}^n\left (\sum_{i=1}^m A_{i,j}y_i\right )x_j\geq \frac{1}{\alpha}\sum_{j=1}^n c_jx_j. \end{aligned}$$

因此

$$\sum_{j=1}^n c_jx_j\leq \alpha \beta \sum_{i=1}^mb_iy_i\leq \alpha\beta\cdot OPT.$$

$\square$

下面我们回到 weighted vertex cover 的问题。并写出它的 linear programming 形式：

$$\begin{aligned} & \min && \sum_{u\in V}C(u)x_u\\ & s.t. && x_u+x_v\geq 1,\ \forall (u,v)\in E\\ & && x_u\geq 0,\ \forall u\in V \end{aligned},\qquad\qquad \begin{aligned} & \max && \sum_{e\in E}y_{e}\\ & s.t. && \sum_{e:e\textbf{关联}u}y_e\leq C(u),\ \forall u\in V\\ & && y_e\geq 0,\ \forall e\in E \end{aligned}$$

注意，理论上$x_u$ 只能选 0,1（即选这个点，或不选这个点）。我们首先把整数规划放松到了线性规划，即把约束$x_u\in\{0,1\}$ 放松到$x_u\geq 0$。

接下来我们利用互补松弛性手动解这个线性规划！（不依赖其他求解器）
我们希望找到 feasible solution $x,y$ 满足以下条件：

• $\forall u\in V$，要么$x_u=0$，要么$\frac{C(u)}{\alpha}\leq \sum_{e\text{关联}u}y_e\leq C(u)$；
• $\forall e=(u,v)\in E$，要么$y_e=0$，要么$1\leq x_u+x_v\leq \beta$。

根据前面的讨论，这样找到的 feasible solution 一定会有$c^Tx\leq \alpha \beta$ 倍的最优解，也就是找到了个近似解。

我们取$\alpha=1,\beta=2$ 为例。即上面的互补松弛性条件变成：

• $\forall u\in V$，要么$x_u=0$，要么$\sum_{e\text{关联}u}y_e= C(u)$；
• $\forall e=(u,v)\in E$，要么$y_e=0$，要么$1\leq x_u+x_v\leq 2$。

然后求解的算法过程如下。我们以一个例子来阐述这个过程。

1. 初始化地，令所有$x_u=y_e=0$。此时它们不是 feasible solution，但平凡地满足互补松弛性条件。
2. 选择一条未被 cover 的边$e$，譬如例子中是$e=AB$。我们增长$y_e$，直到某一个点$u\in V$ 满足了$\sum_{e\text{关联}u}y_e=C(u)$。在这个例子中，就会有$y_e=1$，此时顶点$A,B$ 都满足了

$$\begin{aligned} & A: y_{AB}+y_{AC}+y_{AF}+y_{AG}+y_{AH}=C(A)=1,\\ & B: y_{AB}+y_{BD}+y_{BC}=C(B)=1. \end{aligned}$$

3. 然后我们令那些满足$\sum_{e\text{关联}u}y_e=C(u)$ 的顶点$u\in V$ 的$x_u=1$。
4. 重复 2-3 这个过程。

不难发现，整个过程下面互补松弛性的子条件都是满足的：

• $\forall u\in V$，要么$x_u=0$，要么$\sum_{e\text{关联}u}y_e= C(u)$；
• $\forall e=(u,v)\in E$，要么$y_e=0$，要么$x_u+x_v\leq 2$。

因为$x_u+x_v\leq 2$ 是平凡满足的。我们实际上不断寻找未被 cover 的边，重复 2-3 过程，就是为了让$x$ 成为一个 feasible solution，即满足$1\leq x_u+x_v$ 的部分。

我们可以继续完成上面的例子。第二次重复时，就会选中边$DE$，然后令$y_{DE}$ 增长到$C(D)=1$。此时顶点$D,E$ 都满足

$$\begin{aligned} & D: y_{BD}+y_{DE}=C(D)=1\\ & E: y_{DE}+y_{CE}=C(E)=1 \end{aligned}$$

注意，此时只有$y_{AB}=y_{DE}=1$，其余$y_e=0$。然后我们把$x_D,x_E$ 都设为 1。

重复 2 轮后，已经没有未被 cover 的边了。此时我们可以得到一个 feasible solution：

$$x_F=x_G=x_H=x_C=0,\qquad x_A=x_B=x_D=x_E=1.$$

然后可以得到一个 2 - 近似的结果，因为这个 feasible solution 是完全符合互补松弛性条件的。