A tight semidefinite relaxation for the vertex conver problem
J4
• Original Articles • Previous Articles Next Articles
WANG Xin-hui;LIU San-yang,LIU Hong-wei
Received:
Revised:
Online:
Published:
Abstract: 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.
Key words: vertex cover problem, semidifinite programming, tight semidefinite relaxation
CLC Number:
WANG Xin-hui;LIU San-yang;LIU Hong-wei.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://journal.xidian.edu.cn/xdxb/EN/
https://journal.xidian.edu.cn/xdxb/EN/Y2005/V32/I6/958
The condition for generalized saddle points for multiobjective optimization problems in topological vector space
Nonlinear programming method for time optimal switching control
A cut-plane algorithm for semidefinite programming and its application
Cited