Connections between semidefinite relaxations of the max-cut and stable set problems
Laurent, Monique
Poljak, Svatopluk
Rendl, Franz

Data: 1997
Resum: 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. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Max-cut problem ; Stable set problem ; Semidefinite relaxations
Publicat a: Mathematical Programming, vol. 77 n. 2 (1997) p. 225-246, ISSN 0025-5610

22 p, 939.0 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir