CONNECTIONS BETWEEN SEMIDEFINITE RELAXATIONS OF THE MAX-CUT AND STABLE SET PROBLEMS

We describe links between a recently introduced semidefinite relaxatio n for the max-cut problem and the well known semidefinite relaxation f or the stable set problem underlying the Lovasz's theta function, It t urns out that the connection between the convex bodies defining the se midefinite relaxations mimics the connection existing between the corr esponding polyhedra. We also show how the semidefinite relaxations can be combined with the classical linear relaxations in order to obtain tighter relaxations. (C) 1997 The Mathematical Programming Society, In c. Published by Elsevier Science B.V.