A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations.
DOI:
关键词:
摘要:
参考文章(13)
Michael Jünger, Giovanni Rinaldi, Relaxations of the Max Cut Problem and Computation of Spin Glass Ground States Operations Research Proceedings. pp. 74- 83 ,(1998) , 10.1007/978-3-642-58891-4_11
Steven J. Benson, Yinyu Yeb, Xiong Zhang, Mixed linear and semidefinite programming for combinatorial and quadratic optimization Optimization Methods & Software. ,vol. 11, pp. 515- 544 ,(1999) , 10.1080/10556789908805761
Michel X. Goemans, David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Journal of the ACM. ,vol. 42, pp. 1115- 1145 ,(1995) , 10.1145/227683.227684
Uriel Feige, Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut Random Structures and Algorithms. ,vol. 20, pp. 403- 440 ,(2002) , 10.1002/RSA.10036
John E. Mitchell, Computational Experience with an Interior Point Cutting Plane Algorithm Siam Journal on Optimization. ,vol. 10, pp. 1212- 1227 ,(1999) , 10.1137/S1052623497324242
Stefan Feltenmark, Krzysztof C. Kiwiel, Dual Applications of Proximal Bundle Methods, Including Lagrangian Relaxation of Nonconvex Problems Siam Journal on Optimization. ,vol. 10, pp. 697- 721 ,(1999) , 10.1137/S1052623498332336
Francisco Barahona, Ali Ridha Mahjoub, On the cut polytope Mathematical Programming. ,vol. 36, pp. 157- 173 ,(1986) , 10.1007/BF02592023
Hanif D. Sherali, Warren P. Adams, A hierarchy of relaxation between the continuous and convex hull representations SIAM Journal on Discrete Mathematics. ,vol. 3, pp. 411- 430 ,(1990) , 10.1137/0403036
Francisco Barahona, Ranga Anbil, The volume algorithm: producing primal solutions with a subgradient method Mathematical Programming. ,vol. 87, pp. 385- 399 ,(2000) , 10.1007/S101070050002
Monique Laurent, Svatopluk Poljak, Franz Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems Mathematical Programming. ,vol. 77, pp. 225- 246 ,(1997) , 10.1007/BF02614436