Connections between semidefinite relaxations of the max-cut and stable set problems
Mathematical Programming , Volume 77 p. 225- 246
We describe the links existing between a recently introduced semidefinite relaxation for the max-cut problem and the well known semidefinite relaxation for the stable set problem underlying the Lovász's theta function. It turns out that the connection between the convex bodies defining the semidefinite relaxations mimicks the connection existing between the corresponding polyhedra. We also show how the semidefinite relaxations can be combined with the classical linear relaxations in order to obtain tighter relaxations.
|stable set, max-cut, semidefinite programming|
|Logistics (theme 3)|
|Organisation||Networks and Optimization|
Laurent, M, Poljak, S, & Rendl, F. (1997). Connections between semidefinite relaxations of the max-cut and stable set problems. Mathematical Programming, 77, 225–246.