Connections between semidefinite relaxations of the max-cut and stable set problems
作者： Monique Laurent , Svatopluk Poljak , Franz Rendl
DOI: 10.1007/BF02614436
关键词: Theta function 、 Connection (vector bundle) 、 Maximum cut 、 Combinatorics 、 Relaxation (approximation) 、 Mathematics 、 Semidefinite programming 、 Polyhedron 、 Independent set 、 Discrete mathematics 、 Regular polygon
摘要: We describe links between a recently introduced semidefinite relaxation for the max-cut problem and well known stable set underlying Lovasz's theta function. It turns out that connection convex bodies defining relaxations mimics existing corresponding polyhedra. also show how can be combined with classical linear in order to obtain tighter relaxations.
springer.com
uab.cat
narcis.nl参考文章(25)
Egon Balas, Sebastián Ceria, Gérard Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs Mathematical Programming. ,vol. 58, pp. 295- 324 ,(1993) , 10.1007/BF01581273
Monique Laurent, Svatopluk Poljak, On the facial structure of the set of correlation matrices SIAM Journal on Matrix Analysis and Applications. ,vol. 17, pp. 530- 547 ,(1996) , 10.1137/0617031
Svatopluk Poljak, Zsolt Tuza, The expected relative error of the polyhedral approximation of the max-cut problem Operations Research Letters. ,vol. 16, pp. 191- 198 ,(1994) , 10.1016/0167-6377(94)90068-X
P. L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0–1 optimization Mathematical Programming. ,vol. 28, pp. 121- 155 ,(1984) , 10.1007/BF02612354
Robert Grone, Charles R. Johnson, Eduardo M. Sá, Henry Wolkowicz, Positive definite completions of partial Hermitian matrices Linear Algebra and its Applications. ,vol. 58, pp. 109- 124 ,(1984) , 10.1016/0024-3795(84)90207-6
Jon Kleinberg, Michel X. Goemans, The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover SIAM Journal on Discrete Mathematics. ,vol. 11, pp. 196- 204 ,(1998) , 10.1137/S0895480195287541
Francisco Barahona, Ali Ridha Mahjoub, On the cut polytope Mathematical Programming. ,vol. 36, pp. 157- 173 ,(1986) , 10.1007/BF02592023
Monique Laurent, Svatopluk Poljak, On a positive semidefinite relaxation of the cut polytope Linear Algebra and its Applications. pp. 439- 461 ,(1995) , 10.1016/0024-3795(95)00271-R
Egon Balas, Sebastian Ceria, Gerard Cornuejols, Gabor Pataki, Polyhedral Methods for the Maximum Clique Problem Cliques, Coloring, and Satisfiability. pp. 11- 28 ,(1994) , 10.21236/ADA298925
Francisco Barahona, On cuts and matchings in planar graphs Mathematical Programming. ,vol. 60, pp. 53- 68 ,(1993) , 10.1007/BF01580600