J4

• Original Articles • Previous Articles     Next Articles

A tight semidefinite relaxation for the vertex conver problem

WANG Xin-hui;LIU San-yang,LIU Hong-wei

  

  1. (School of Science, Xidian Univ., Xi′an 710071, China)
  • Received:1900-01-01 Revised:1900-01-01 Online:2005-12-20 Published:2005-12-20

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: 

  • O221.2