摘要
对顶点覆盖问题的一种等价模型,利用一般的松弛方法,得到了一个半定规划松弛模型.通过引入算子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.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2005年第6期958-960,964,共4页
Journal of Xidian University
基金
国家自然科学基金资助项目(69972036)
陕西省自然科学基金资助项目(2000SL03)
关键词
顶点覆盖问题
半定规划
强化半定规划松弛
vertex cover problem
semidifinite programming
tight semidefinite relaxation