顶点覆盖问题的强化半定规划松弛

A tight semidefinite relaxation for the vertex conver problem

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

A semidefinite relaxation is attained from the equivalence form for the Vertex Cover Problem in a normal way. A tight semidifinite relaxation is achieved by defining the operator hsvec. It is shown that the tight semidefinite relaxation provides a sharp lower bound. A numerical example is given.