| 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: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.  |
| 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 |
visitant ::
identificació
Accés restringit a la UAB
