详细内容参考：《算法导论 第二版-中文版》第644页内容
一，基本介绍
1，点覆盖问题属于NPC问题，目前还没有多项式时间算法精确地求解该问题。因而，下面介绍了一种近似解法，可以在多项式时间内找到点覆盖问题的一个近似解，该近似解有多么近似呢？最后证明该近似解不会超过精确解的两倍。
2，点覆盖的定义：
对于图G=(V,E)，点覆盖是由G中的顶点组成的一个集合。该集合中的点关联了图G中所有的边（即，从图G中任取一条边(u,v)，该边关联点两个顶点：顶点u 和 顶点v 。则，u、v 中至少有一个在点覆盖集合中）。
注意：1）点覆盖中的点是可以邻接的。2）点覆盖必须要覆盖图中所有的边。3）最小点覆盖即寻找一个具有顶点数目最少的点覆盖集合
二，利用线性规划来建模最小带权点覆盖问题
1，对于图G=(V,E)，对图中每一个顶点v belongs to V，定义函数 x(v) belongs to [0,1]，且 x(v) = 0表示顶点v不在点覆盖中； x(v) = 1 表示顶点v在点覆盖中。
2，对图中任一条边(u,v) belongs to E，由点覆盖定义，顶点u、顶点v 至少有一个必须在点覆盖中 ，因此：x(u) + x(v) >=1
因而得到最小权值点覆盖的规划模型：其中w(v) 表示顶点v的权值。
而在实际的问题中，x(v)只能取0或者1，这里用 0<=x(v)<=1 替代它，这是可以的。因为：前者是后者的一个特例。前者称为0-1整数规划，后者为普通的线性规划。因此，线性规划中的最优解是0-1整数规划最优解的一个下界（因为线性规划最优解包含了0-1整数规划最优解）。
而求最小权值点覆盖问题的最优解即为求0-1整数规划问题的最优解，因此，线性规划中的最优解是最小权值点覆盖问题的最优解的一个下界。
三，用线性规划的解来构造最小权值点覆盖问题的近似解算法
伪代码参考：《算法导论 第二版-中文版》第645页内容
对于每一个顶点v，都会求得一个x(v)的值。若，x(v)>=1/2 ,则将该顶点加入到点覆盖集合中，否则舍去顶点v，直至图G中所有的顶点都处理完毕。此时得到的顶点集合C即为最小权值点覆盖问题的近似解的点覆盖集合。
四，证明第三步中求得的顶点集合C是最小权值点覆盖问题的二倍近似解
设 C* 是最小权值点覆盖问题的一个最优解，Z 是线性规划的一个最优解， C是最小权值点覆盖问题的近似解
1）由于最小权值点覆盖问题的一个最优解是线性规划的一个可行解，故：Z<=W(C*)（W为求权值的函数）
2) 为什么第三步中求得的集合C就是一个点覆盖呢？因为对任意边(u,v) belongs to E,有x(u)+x(v)>=1，即在x(u)和x(v)中至少有一个的值大于1/2。因此，顶点u、v 至少有一个会被加入到集合C中，从而使得图G中的每一条边都会被覆盖。
3）由：
及Z<=W(C*)
知：W(C)<= 2Z <=2W(C*) 即近似解C的权值W(C) 小于等于 二倍最优解C*的权值.