Connections between semidefinite relaxations of the max-cut and stable set problems

Connections between semidefinite relaxations of the max-cut and stable set problems

0.00 Avg rating0 Votes
Article ID: iaor19981383
Country: Netherlands
Volume: 77
Issue: 2
Start Page Number: 225
End Page Number: 246
Publication Date: May 1997
Journal: Mathematical Programming
Authors: , ,
Keywords: graphs
Abstract:

We describe links 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 mimics 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.

Reviews

Required fields are marked *. Your email address will not be published.