Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
作者： Samuel Burer , Renato D. C. Monteiro , Yin Zhang
DOI: 10.1137/S1052623400382467
关键词: Heuristic 、 Maximum cut 、 Semidefinite programming 、 Mathematics 、 Randomized algorithm 、 Quadratically constrained quadratic program 、 Relaxation (approximation) 、 Mathematical optimization 、 Approximation algorithm 、 Heuristics
摘要: … In this section, we focus on extending the rank-two relaxation idea to a close relative of MAX-CUT—the MAX-BISECTION problem. MAX-BISECTION is the same as MAX-CUT except …
acm.org
aip.org
rice.edu 参考文章(26)
Vanderbei Robert, Benson Hande Yurttan, On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems Center for Discrete Mathematics & Theoretical Computer Science. ,(2000)
C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt, G. Rinaldi, Exact Ground States of Ising Spin Glasses: New Experimental Results With a Branch and Cut Algorithm Journal of Statistical Physics. ,vol. 80, pp. 487- 496 ,(1995) , 10.1007/BF02178370
Samuel Burer, Renato D.C. Monteiro, Yin Zhang, Interior-Point Algorithms for Semidefinite Programming Based on A Nonlinear Programming Formulation ,(1999)
Hanno Lefmann, Thomas Hofmeister, Oliver Dolezal, A Comparison of Approximation Algorithms for the MaxCut-Problem Universität Dortmund. ,(2001) , 10.17877/DE290R-5013
A. Frieze, M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION Algorithmica. ,vol. 18, pp. 67- 81 ,(1997) , 10.1007/BF02523688
Bernd A. Berg, Tarik Celik, New approach to spin-glass simulations Physical Review Letters. ,vol. 69, pp. 2292- 2295 ,(1992) , 10.1103/PHYSREVLETT.69.2292
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
K. Binder, A. P. Young, Spin glasses: Experimental facts, theoretical concepts, and open questions Reviews of Modern Physics. ,vol. 58, pp. 801- 976 ,(1986) , 10.1103/REVMODPHYS.58.801
Samuel Burer, Renato D. C. Monteiro, A projected gradient algorithm for solving the maxcut SDP relaxation Optimization Methods & Software. ,vol. 15, pp. 175- 200 ,(2001) , 10.1080/10556780108805818