近似算法介绍
Published:
《研究生算法设计》课程报告
摘要
本文首先通过NP完全问题的求解方式引入近似算法，然后介绍近似算法的基本概念，接下来介绍近似算法的性能即近似度的计算方式，随后以顶点覆盖问题、旅行商问题、集合覆盖问题和子集和问题几个实际的近似算法求解的问题为例详细介绍近似算法，之后简要介绍设计近似算法的另两种非常有效的技术随机化和线性规划，最后对本文内容进行总结，并给出课后习题。
问题引入
现实生活中，许多问题都是NP完全问题，其存在难以获得最优解，但具有极高解题实际意义的特点。因此，虽然不能找到能给出问题准确解的多项式时间算法，但也有其他方法能够在一定程度上解决问题，可能的方法有以下三种：
如果实际输入的规模比较小，则使用指数时间的算法解决问题。
将一些重要的、多项式时间可解的特殊情况隔离出来。
可能在多项式时间内找到（最坏情况或平均情况）近似最优解。
实际生产生活中，许多情况下近似最优解就可以满足需要，这种能返回近似最优解的算法被称为近似算法，也就是本文将要介绍的算法。
近似算法基本思想
在对问题的求解中，对算法的评估主要参照下列三个方面：
解的优越性，即是否能达到最优解；
算法的效率，即复杂度（能否在多项式时间内完成）；
算法适用的范围，即是否适用于所有情况，还是只适合特殊情形。
近似算法就是放宽第一条要求，通过放弃对最优解的求解，使用近似最优解来替代最优解，从而达到算法设计上的简化与时间复杂性的降低，并满足算法使用范围，其目标要满足以下三个条件
能够在多项式时间内高效运行；
能够给出最优解；
对于每个问题实例均有效。
在设计近似算法时，常用的方法有：
贪心法：根据人们的日常想法, 构造解的过程视为一个决策序列, 借助排序或者其他 启发式方法进行近似。 (将在本文中重点介绍)
局部搜索：对于一个可行解, 看看其周遭的解是否更好, 如果更好就移动过去. 有时候这个方法可以获得近似保证。
线性规划：组合优化问题很多都可写成整数线性规划。（将在下文中简要介绍）
随机化。（将在下文中简要介绍）
归约。
近似算法性能
衡量近似算法性能的标准有：
时间复杂性必须是多项式阶的。这是近似算法的基本目标；
解的近似程度。这是近似算法的重要目标。
近似比
我们设$A$是一个多项式时间算法，且对组合优化问题$\Pi$的每一个实例$I$输出一个可行解$\sigma$，记$A(I)=c(\sigma)$，$c(\sigma)$是可行解$\sigma$的值。设最优化算法为$OPT$，即当$A(I)=OPT(I)$时，$A$总是输出$I$的最优解。
当$\Pi$是最小化问题时，记$r_A(I)=\frac{A(I)}{OPT(I)}$；
当$\Pi$是最大化问题时，记$r_A(I)=\frac{OPT(I)}{A(I)}$；
对每一个实例$I$，有$r_A(I)\leq r$，则称$A$的近似比为$r$，$A$是$r$-近似算法，近似比越高，近似比越大，近似解与最优解的近似程度越低，近似算法效果越差。
相对误差与相对误差界
| 沿用上文的假设，$A$的相对误差为$\frac{ | A-OPT | }{OPT}$，有$\frac{ | A-OPT | }{OPT} \leq \epsilon (n)$，称$\epsilon (n)$是$A$的相对误差界。 |
| 当$\Pi$是最小化问题时，记$\epsilon (n)=\frac{ | A-OPT | }{OPT}=\frac{A-OPT}{OPT}=\frac{A}{OPT}-1=r_A(I)-1$； |
| 当$\Pi$是最大化问题时，记$\epsilon (n)=\frac{ | A-OPT | }{OPT}=\frac{OPT-A}{OPT}=\frac{\frac{OPT}{A}-1}{\frac{OPT}{A}}=\frac{r_A(I)-1}{r_A(I)} \leq r_A(I)-1$； |
通过近似比和相对误差可以判断近似算法与最优解的近似程度，从而衡量近似算法的性能（其中相对误差可以通过近似比得到）。
可近似性分类
按照可近似性可将NP完全的组合优化问题分为3类
完全可近似的：对任意小的$\epsilon>0$，存在$(1+\epsilon)$-近似算法，例如0-1背包问题；
可近似的：存在具有常数比的近似算法，例如顶点覆盖、多机调度、满足三角不等式的旅行商问题；
不可近似的：不存在具有常数比的近似算法，近似比是输入规模的对数多项式或多项式，例如一般性的旅行商问题。
近似算法实例
本节将介绍解决NP完全问题的多项式时间近似算法的几个例子，包括顶点覆盖问题、旅行商问题、集合覆盖问题以及子集和问题。
顶点覆盖问题
顶点覆盖问题是一个NP完全问题。
问题：
给定无向图$G=(V,E)$，求其最小的顶点覆盖。
算法基本流程：
初始化$V’=\emptyset$；
任取一条边$(u,v)$；
把$u$和$v$加入$V’$；
删去$u$和$v$及其关联的边；
重复步骤2、3、4，直至删去所有的边为止，$V’$即为所求的最小顶点覆盖。
伪代码：
::: algorithm :::
算法性能分析：
从算法[al1]{reference-type=”ref” reference=”al1”}中可以看到本近似算法的执行过程，其时间复杂度为$O(V+E)$。
我们假设$OPT$为最优顶点覆盖，$E$为算法步骤2即第5行伪代码中选出的边集，为了覆盖$E$中的边，任意顶点覆盖均需包含$E$中每条边的至少一个顶点，由于$E$中不存在具有共同端点的两条边（这是因为一旦一条边在步骤2中被选出，所有与其顶点关联的边都会被步骤4即第7行伪代码删除），因此最优顶点覆盖的规模下界有， \(\label{e1} |OPT| \geq |E*|\)
而每次执行步骤2，都会选择一条边将其两个顶点加入$C$，则最终返回的顶点覆盖的规模上界有， \(\label{e2} |C| = 2|E*|\)
结合式[e1]{reference-type=”ref” reference=”e1”}、[e2]{reference-type=”ref” reference=”e2”}可得，
\[|C| = 2|E*| \leq 2|OPT|\]则
\[\frac{|C|}{|OPT|} \leq 2\]已知本算法是多项式时间算法，则本算法为多项式时间的2-近似算法。
旅行商问题
问题：
给定完全的无向图$G=(V,E)$，边$(u,v) \in E$有非负整数代价$c(u,v)$，求$G$的一个最小代价的哈密顿回路（即包含图中每个顶点一次的回路）。
在许多情况中，从一个地方直达另一个地方往往是代价最小的，增加中间点的路程会增加代价，我们对这种情况称为代价函数$c$满足三角不等式，即对所有顶点$u,v,w\in V$，有：
\[\label{e3} c(u,w) \leq c(u,v)c(v,w)\]在下文中我们将介绍，对于满足三角不等式的旅行商问题，存在2-近似算法，而对于一般性的旅行商问题则不存在具有常数近似比多项式时间的近似算法（除非$P=NP$）。
满足三角不等式的旅行商问题
算法基本流程：
构建最小生成树；
对最小生成树进行前序遍历构造回路。
伪代码：
此处我们使用Prim算法生成最小生成树。
::: algorithm :::
算法性能分析：
本算法构造最小生成树的时间复杂度为$O(V^2)$，前序遍历的时间复杂度为$O(V)$，则本算法的时间复杂度为$O(V^2)$。
我们假设$OPT$为给定无向图中的最优哈密顿回路，由于需要删除回路中的任一条边得到生成树，则最小生成树的权值是最小代价的一个下界，有，
\[\label{e4} c(T) \leq c(OPT)\]按照算法步骤，我们对$T$进行完全遍历，假设这个遍历为$W$，将经历$T$每条边两次，则有，
\[\label{e5} c(W) = 2c(T)\]结合式[e4]{reference-type=”ref” reference=”e4”}和式[e5]{reference-type=”ref” reference=”e5”}可得，
\[\label{e6} c(W) \leq 2c(OPT)\]由于遍历$W$对某些顶点要访问一次以上，根据三角不等式，我们从$W$中去掉一次对任意顶点的访问，并不会增加代价，将$W$中对每个顶点第一次访问之外的访问去掉后，得到对$T$的前序遍历，设$H$为这个前序遍历的哈密顿回路，则有，
\[\label{e7} c(H) \leq c(W)\]结合式[e6]{reference-type=”ref” reference=”e6”}和式[e7]{reference-type=”ref” reference=”e7”}可得，
\[\label{e8} c(H) \leq 2c(OPT)\]则
\[\label{e9} \frac{H}{OPT} \leq 2\]已知本算法是多项式时间算法，则本算法为多项式时间的2-近似算法。
一般性的旅行商问题
如果我们去掉满足三角不等式的约束，面对一般性的旅行商问题，除非$P=NP$，不存在有常数近似比的多项式时间近似算法，接下来我们将证明这一结论。
要证如果$P \neq NP$，则对任何常数$\rho \geq 1$，一般性的旅行商问题不存在具有近似比$\rho$的多项式时间近似算法。
假设对某个数$1 \leq \rho \leq K$，存在一般性旅行商问题的一个近似比为$\rho$的多项式时间近似算法$A$，任意给定图$G=(V,E)$，构造一般性旅行商问题实例$I_G$如下：有城市集$V$，$\forall \boldsymbol{u}, \boldsymbol{v} \in \boldsymbol{V}$，
| 若$(u, v) \in E$，则令$d(u, v)=1$，否则令$d(u, v)=Kn$，其中$ | V | = n$，若$G$有哈密顿回路，则， |
否则，
\[OPT\left(I_{G}\right)>Kn, \quad A\left(I_{G}\right) \geq OPT\left(I_{G}\right)>Kn\]所以，当且仅当$A\left(I_{G}\right) \leq Kn$时，$G$有哈密顿回路。
则要判断图$G$是否包含一个哈密顿回路，可以首先构造旅行商问题的实例$I_G$，然后对$I_G$运用算法$A$，若$A\left(I_{G}\right) \leq Kn$，则输出”yes”，否则输出”no”。
| 由于$K$是固定的常数，构造$I_G$可以在$O(n^2)$时间内完成，且$ | I_G | =O(n^2)$，$A$是多项式时间算法，对$I_G$可在$n$的多项式时间内完成计算，所以上述判断图中是否有哈密顿回路的算法是多项式时间算法，由于判断图中是否包含哈密顿回路问题是NP完全的，推得$P=NP$。 |
因此得证，除非$P=NP$，不存在一般旅行商问题的具有常数近似比的多项式时间近似算法。
集合覆盖问题
问题：
给定一个有$n$个元素的集合$U={e_1,…,e_n}$，$U$的子集的集合为$S={s_1,…,s_m}$，求一个能覆盖$U$的所有元素的子集$S’\subseteq S$，使$\sum_{S_{i} \in \mathbf{S}^{\prime}} c(S)$最小。
算法基本流程：
选出能覆盖尽可能多的未被覆盖的元素的一个子集；
将该子集覆盖的元素去掉，保存该子集；
重复步骤1、2，直至未被覆盖元素集合为空；
循环结束保存的子集的集合即为近似解。
伪代码：
::: algorithm :::
算法性能分析：
| 算法的时间复杂度为$O( | U | S | min( | U | , | S | ))$。 |
为了证明本近似算法的近似比，我们设每个由该算法选出的集合代价为1，设$s_i$为算法选出的第$i$个子集，在将$s_i$加入$C$时代价为1，将这个选择$S_i$的代价均匀分布于首次被$S_i$覆盖的元素上，设$c_u$为分配给元素$u$的代价，$u\in U$，对每个元素都只分配一次代价，也就是当他第一次被覆盖时分配代价，如果$u$第一次被$s_i$覆盖，则，
\[c_{u}=\frac{1}{\left|s_{i}-\left(s_{1} \cup s_{2} \cup \cdots \cup s_{i-1}\right)\right|}\]在算法的每一步中都要分配1个单位的代价，则有，
\[\label{e10} |\mathcal{C}|=\sum_{u \in U} c_{u}\]分配给最优覆盖的代价为，
\[\sum_{s \in C^{\prime}} \sum_{u \in s} c_{u}\]由于每一个$u \in U$都至少在一个集合 $s \in \mathcal{C}^{*}$中, 因此有，
\[\label{e11} \sum_{s \in c^{\cdot}} \sum_{u \in s} c_{u} \geq \sum_{u \in U} c_{u}\]将式[e10]{reference-type=”ref” reference=”e10”}与式[e11]{reference-type=”ref” reference=”e11”}结合，有，
\[\label{e12} |\mathcal{C}| \leq \sum_{s \in C^{*}} \sum_{u \in s} c_{u}\]对于任何属于$S$的集合$s$有，
\[\label{e13} \sum_{u \in s} c_{u} \leq H(|s|)\]根据式[e12]{reference-type=”ref” reference=”e12”}和式[e13]{reference-type=”ref” reference=”e13”}，可得，
\[|\mathcal{C}| \leq \sum_{s \in C^{*}} H(|s|) \leq \left|\mathcal{C}^{*}\right| \cdot H(\max \{|s|: s \in S\})\]| 由此得到，本算法是一个多项式时间的$\rho(n)$近似算法，$\rho(n)=\left | \mathcal{C}^{*}\right | \cdot H(\max { | s | : s \in S}$。 |
接下来证明式[e13]{reference-type=”ref” reference=”e13”}，对任意集合$s in S$和$i=1,2, \cdots,|\mathcal{C}|$，设$v_{i}=\left|s-\left(s_{1} \cup s_{2} \cup \cdots \cup s_{i}\right)\right|$为$s_{1}, s_{2}, \cdots, s_{i}$被该算法选出之后，$S$中余下的末被覆盖的元素个数。定义$v_{0}=|s|$为$s$中元素（开始时它们都末被覆盖）的个数。设$k$为满足$v_{k}=0$的最小下标，使得$s$的每个元素至少被集合$s_{1}, s_{2}, \cdots, s_{k}$中之一所覆盖。这样，对$i=1,2, \cdots, k, v_{i-1} \geq v_{i}$，且$s$中共有$v_{i-1}-v_{i}$个元素首次被$s_{i}$所覆盖，于是有，
\[\sum_{u \in s} c_{u}=\sum_{i=1}^{k}\left(v_{i-1}-v_{i}\right) \cdot \frac{1}{\left|s_{i}-\left(s_{1} \cup s_{2} \cup \cdots \cup s_{i-1}\right)\right|}\]注意到，
\[\left|S_{i}-\left(S_{1} \cup S_{2} \cup \cdots \cup S_{i-1}\right)\right| \geq\left|S-\left(S_{1} \cup S_{2} \cup \cdots \cup S_{i-1}\right)\right|=u_{i-1}\]这是因为对$s_{i}$的贪心选择保证了$s$不可能比$s_{i}$覆盖更多的元素（否则, 选出的就会是$s$，而不是$s_{i}$）。由此可得，
\[\sum_{u \in s} c_{u} \leq \sum_{i=1}^{k}\left(v_{i-1}-v_{i}\right) \cdot \frac{1}{v_{i-1}}\]则可以给出这个量的界，
\[\begin{array}{l}\\\sum_{u \in s} c_{u} \leq \sum_{i=1}^{k}\left(v_{i-1}-v_{i}\right) \cdot \frac{1}{v_{i-1}} \\\\=\sum_{i=1}^{k} \sum_{j=v_{i}+1}^{k_{i-1}} \frac{1}{v_{i-1}} \\\\\leq \sum_{i=1}^{k} \sum_{j=v_{i}+1}^{v_{i}-1} \frac{1}{j} \quad\left(\text { 由于 } j \leq v_{i-1}\right. \text { ) } \\\\=\sum_{i=1}^{k}\left(\sum_{j=1}^{v_{i+1}} \frac{1}{j}-\sum_{j=1}^{v_{i}} \frac{1}{j}\right) \\\\=\sum_{i=1}^{k}\left(H\left(u_{i-1}\right)-H\left(v_{i}\right)\right) \\\\=H\left(v_{0}\right)-H\left(v_{k}\right) \quad \text { (根据和的叠缩） } \\\\=H\left(v_{0}\right)-H(0) \\\\=H\left(v_{0}\right) \quad(\text { 由于 } H(0)=0 \text { ) } \\\\=H(|S|), \\\\\end{array}\]则完成了对式[e13]{reference-type=”ref” reference=”e13”}的证明。
| 由于本算法是一个多项式时间的$\rho(n)$近似算法，$\rho(n)=\left | \mathcal{C}^{*}\right | \cdot H(\max { | s | : s \in S}$，且有， |
| 可得，本算法为多项式时间的$(ln | U | +1)$近似算法。 |
子集和问题
问题：
给定正整数集合$S={x_1,x_2,…,x_n}$和正整数$t$，求$S$的一个子集，其中的元素之和在不超过目标值$t$的情况下最大。
指数级时间的准确算法： 我们计算集合$S$每个子集$S’$中所有元素的和，在元素和不超过$t$的子集中，选择和最接近$t$的子集，则可以得到最优解，但可能需要指数级的时间，可能的算法流程伪代码如下（其中在合并两个排序列表时使用归并排序的方法），
::: algorithm :::
完全多项式时间近似算法：
在准确算法的基础上，我们做出调整以达到降低时间复杂度的效果，在每个列表$L_i$创建后对其进行”修整”，就是说在寻找近似解的过程中，如果$L$中的两个数比较接近，则没必要同时保存两个数，即设置一个修整参数$\delta$，满足$0<\delta<1$，设$L’$为$L$修整后的结果，则对于从$L$中去除的每个元素$y$，都存在一个仍在$L’$中的，近似$y$的元素$z$，有，
\[\frac{y}{1+\delta} \leq z \leq y\]下面我们给出修整的伪代码算法[al5]{reference-type=”ref” reference=”al5”}（所输入的$L$已按照递增排序），
::: algorithm :::
这一步时间复杂度为$O(m)$。接下来可以进行子集和问题的近似求解，给定近似参数$\epsilon$，有$0<\epsilon<1$，得到的值落在最优解的$1+\epsilon$倍内，下列给出近似算法的伪代码算法[al6]{reference-type=”ref” reference=”al6”}。
::: algorithm :::
算法性能分析：
我们设$y^* \in P_n$为子集和问题的一个最优解，则有$z^* \leq y^*$，对$i$进行数学归纳法证明，可证得，对于准确算法中子集和中的每个至多为$t$的元素$y$，存在一个$z \in L_i$，使得，
\[\label{e14} \frac{y}{(1+\epsilon / 2 n)^{i}} \leq z \leq y\]式[e14]{reference-type=”ref” reference=”e14”}对$y^* \in P_n$成立，则存在一个$z \in L_i$，使得，
\[\frac{y^*}{(1+\epsilon / 2 n)^{i}} \leq z \leq y^*\]有
\[\label{e15} \frac{y^{*}}{z} \leq\left(1+\frac{\epsilon}{2 n}\right)^{n}\]式[e15]{reference-type=”ref” reference=”e15”}对$z^$成立，而$z^$是$L_n$中的最大值，则，
\[\label{e16} \frac{y^{*}}{z^{*}} \leq\left(1+\frac{\epsilon}{2 n}\right)^{n}\]因为有$\frac{d}{d n}\left(1+\frac{\epsilon}{2 n}\right)^{n}>0$以及$\lim _{n \rightarrow \infty}(1+\frac{\epsilon}{2 n})^{n}=e^{\frac{\epsilon}{2}}$，则说明函数$(1+\frac{\epsilon}{2 n})^{n}$在接近极限$e^{\frac{\epsilon}{2}}$的过程中，随$n$的增长而增长, 于是有，
\[\label{e17} \begin{aligned} \left(1+\frac{\epsilon}{2 n}\right)^{n} & \leq e^{\frac{\epsilon}{2}} & & \\ & \leq 1+\frac{\epsilon}{2}+(\frac{\epsilon}{2})^{2} \\ & \leq 1+\epsilon \end{aligned}\]由式[e16]{reference-type=”ref” reference=”e16”}和式[e17]{reference-type=”ref” reference=”e17”}可得本算法的近似比为$1+\epsilon$。
已知修整后，$L_i$中连续的元素$z$与$z’$存在关系$\frac{z’}{z}>1+\frac{\epsilon}{2 n}$，也就是说他们之间相差的倍数至少为$1+\frac{\epsilon}{2 n}$，所以, 每个列表都包含了值0，有可能还包含了值1，以及$\left\lfloor\log _{1+\frac{\epsilon}{2 n}} t\right\rfloor$个其他的值，每个列表$L_i$中的元素数最多为，
\[\begin{aligned} \log _{1+\frac{\epsilon}{2 n}} t+2 & =\frac{\ln t}{\ln (1+\frac{\epsilon}{2 n})}+2 \\ & \leq \frac{2 n(1+\frac{\epsilon}{2 n}) \ln t}{\epsilon}+2 \\ & \leq \frac{4 n \ln t}{\epsilon}+2 \end{aligned}\]而本算法的时间复杂度为$L_i$长度的多项式，则本算法是一个完全多项式时间的近似算法。
随机化和线性规划
随机化——MAX-3-CNF
我们将通过给出3-CNF可满足性的最优化版本的一个随机化算法为例，介绍随机化方法在近似算法设计中的应用。
问题：
找到变量的一种赋值，使得有尽可能多的子句得到满足。
随机化算法：
以$\frac{1}{2}$的概率将每个变量设为$1$；
以$\frac{1}{2}$的概率将每个变量设为$0$。
上述步骤即可得到随机化的$\frac{8}{7}$近似算法。
算法性能分析：
假设我们已经以概率$\frac{1}{2}$独立地将每个变量设置为$1$，以概率$\frac{1}{2}$独立地将每个变量设置为$0$，对$i=1,2, \cdots, n$，定义指示器随机变量$Y_{i}=I{\text {子句} i \text {被满足}}$。
则只要第$i$个子句的变量中，至少有一个已被置为$1$，就有$Y_{i}=1$。由于在同一个子句中, 任何一个变量的出现次数都不会多于一次，而我们已经假设了同一子句中不会同时出现一个变量及其否定形式，所以每个子句中三个变量的设置都是互相独立的。对于一个子句来说，只有当它的三个变量都被置为$0$时，才不会被满足，因此$\operatorname{Pr}{ \text{子句} i \text{不被满足} }=(\frac{1}{2})^{3}=\frac{1}{8}$。于是，$\operatorname{Pr}{ \text{子句} i \text{被满足} }=1-\frac{1}{8}=\frac{7}{8}$。有$E \left[Y_{i}\right]=\frac{7}{8}$。设$Y$为得到满足的子句的总数, 有$Y=Y_{1}+Y_{2}+\cdots+Y_{m}$。于是，有，
\[\begin{aligned}\mathrm{E}[Y] & =\mathrm{E}\left[\sum_{i=1}^{m} Y_{i}\right]=\sum_{i=1}^{m} \mathrm{E}\left[Y_{i}\right] \quad \text { （根据期望的线性性质） } \\ & =\sum_{i=1}^{m} \frac{7}{8}=\frac{7m}{8} \end{aligned}\]$m$是得到满足的子句数量的一个上界, 因而, 近似比最多为$\frac{m}{\frac{7m}{8}}=\frac{8}{7}$。
线性规划——带权顶点覆盖
我们将通过给出求解带权顶点覆盖问题的一个线性规划算法为例，介绍线性规划方法在近似算法设计中的应用。
问题：
给定无向图$G=(V,E)$，其中每个顶点$v \in V$都有一个关联的正的权值$w(v)$，求其具有最小权值的顶点覆盖。
线性规划算法：
我们将利用线性规划技术，计算出其权值的一个下界。然后，对计算出来的结果进行”舍入”，并利用它来获得一个 顶点覆盖。
假设对每一个顶点$v \in V$，都安排一个变量$x(v)$与之关联，并且，要求对每一个顶点$v \in V$，有$x(v) \in[0,1]$。将$x(v)=1$解释为$v$在顶点覆盖中，将$x(v)=0$解释为$v$不在顶点覆盖中。那么我们可以得出，对于任意边$(u, v)$，$u$和$v$之中至少有一个必须在顶点覆盖中，即$x(u)+x(v) \geq 1$。这样我们就可以将问题描述为一个0-1整数规划问题如下。
\[\text{最小化}\sum_{v \in V} w(v) x(v)\]约束为
\[\begin{array}{ll} x(u)+x(v) \geq 1 & \text { 对每一个 } v \in V \\ x(v) \in\{0,1\} & \text { 对每一个 } v \in V \end{array}\]已知解决上述问题是NP难的，因此我们假设去掉$x(v) \in{0,1}$这一限制，用$0\leq x(v) \leq 1$来替代，从而得到线性规划如下（这就是线性规划松弛），
\[\text { 最小化 } \sum_{v \in V} w(v) x(v)\]约束为
\[\label{e20} \begin{array}{ll} x(u)+x(v) \geq 1 & \text { 对每一个 } v \in V \\ x(v) \leq 1 & \text { 对每一个 } v \in V \\ x(v) \geq 0 & \text { 对每一个 } v \in V \end{array}\]伪代码：
我们利用上述线性规划的解，构造带权顶点覆盖问题的一个近似解，也就是对线性规划的解进行四舍五入，从而得到0-1整数规划的解。
::: algorithm :::
算法性能分析：
设$C^$为最小带全顶点覆盖问题的一个最优解，设$z^$为上述线性规划问题的一个最优解，由于最优顶点覆盖是该线性规划的可行解，因此有，
\[\label{e21} z^* \leq w(C^*)\]接下来，我们通过对变量$\bar{x}(v)$的小数部分进行四舍五入，得到一个集合$C$，它是一个顶点覆盖，并且满足$w(C) \leq 2 z^{*}$。根据式[e20]{reference-type=”ref” reference=”e20”}我们知道，$x(u)+x(v) \geq 1$，表示在$\bar{x}(u)$和$\bar{x}(v)$中，至少有一个其值至少为$\frac{1}{2}$。因此，$u$和$v$两者之中，至少有一个将被加入到顶点覆盖中, 因此每一条边都将被覆盖。
覆盖的权值有，
\[\label{e22} \begin{aligned} z^{*} & =\sum_{v \in V} w(v) \bar{x}(v) \geq \sum_{v \in V_{1} \bar{x}(v) \geq 1 / 2} w(v) \bar{x}(v) \geq \sum_{v \in V_{1} \bar{x}(v) \geq 1 / 2} w(v) \cdot \frac{1}{2} \\ & =\sum_{v \in C} w(v) \cdot \frac{1}{2} =\frac{1}{2} \sum_{v \in c} w(v) =\frac{1}{2} w(C) \end{aligned}\]结合式[e21]{reference-type=”ref” reference=”e21”}和式[e22]{reference-type=”ref” reference=”e22”}可得，
\[w(C) \leq 2 z^{*} \leq 2 w\left(C^{*}\right)\]则本算法为2近似算法。
总结
近似算法是解决NP难问题的方法之一，他通过放弃对最优解的求解，使用近似最优解来替代最优解，从而达到算法设计上的简化与时间复杂性的降低，并满足算法使用范围，在设计近似算法时常见的方法有贪心法、局部搜索、基于线性规划的方法、随机化、归约......分析近似算法性能的指标主要为其近似比。
证明某一问题除非$P=NP$，不存在常数近似比的多项式时间近似算法的一种通用方法是：给定一个NP难的问题$X$，我们可以构造一个最小化问题$Y$，使得$X$的"yes"实例对应于$Y$的值最多为$k$的实例，而$X$的"no"实例对应于$Y$的值大于$\rho k$的实例，那么我们就证明了除非$P=NP$，问题$Y$不存在$\rho$近似算法。
练习题
装箱问题
有$n$个重量分别为$w_{1}, \ldots, w_{n} \in \mathbb{Z}_{\geq 1}$的物品要装入一系列载重量为$W$的卡车中，如何使用尽量少的卡车完成装箱？请给出近似算法并计算近似比。
背包问题
给定$n$件物品和一个背包，物品$i$的重量为$w_i$，价值为$v_i$，背包的重量限制为$B$，$w_i,v_i,B$都是正整数，把哪些物品装进背包，能在不超过重量限制的条件下使得整体价值最大？请给出近似算法并计算近似比。
k-聚类问题
满足非负性、对称性和三角不等式的条件下有$n$个点$p_{1}, \ldots, p_{n}$，如何找到$k$个中心点$c_{1}, \ldots, c_{k}$来尽可能最小化： \(r=\max _{p_{i}} \min _{c_{j}} d\left(p_{i}, c_{j}\right)\) 请给出近似算法并计算近似比。
多机调度问题
任给有穷的作业集$A$和$m$台相同的机器，作业$a$的処理时间为正整数$t(a)$，每一项作业可以在任一台机器上处理. 如何把作业分配给机器才能使完成所有作业的时间最短? 请给出近似算法并计算近似比。
快慢多机调度问题
如果给定$m$台机器A，$n$台机器B，同一作业$a$在机器A上的処理时间为$t(a)$，在机器B上的处理时间为$\frac{t(a)}{2}$. 如何把作业分配给机器才能使完成所有作业的时间最短？请给出近似算法并计算近似比。