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

A tight semidefinite relaxation for the vertex conver problem

作　　者：王新辉[1] 刘三阳[1] 刘红卫[1] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071

出　　处：《西安电子科技大学学报》2005年第6期958-960,964,共4页Journal of Xidian University

基　　金：国家自然科学基金资助项目(69972036);陕西省自然科学基金资助项目(2000SL03)

摘　　要：对顶点覆盖问题的一种等价模型,利用一般的松弛方法,得到了一个半定规划松弛模型.通过引入算子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.

关 键 词：顶点覆盖问题 半定规划 强化半定规划松弛 

分 类 号：O221.2[理学—运筹学与控制论]