近似算法的顶点覆盖问题的近似算法

问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。

VertexSet approxVertexCover ( Graph g )

{ cset=NULL；

e1=g.e；

while (e1 !=NULL) {

从e1中任取一条边(u,v)；

cset=cset∪{u,v}；

从e1中删去与u和v相关联的所有边；

}

return c

}

Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。

图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。

对顶点覆盖问题的一种等价模型，利用一般的松弛方法，得到了一个半定规划松弛模型；通过引入算子 ，把这个等价模型进行提升，得到了一个强化半定规松弛模型.并从理论上证明了所得到强化松弛模型能比一般松弛模型提供更好的下界，同时数值实验也证明了这一点.

---