A projected gradient algorithm for solving the maxcut SDP relaxation

作     者：Burer, S Monteiro, RDC 

作者机构：Georgia Inst Technol Sch Math Atlanta GA 30332 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《OPTIMIZATION METHODS & SOFTWARE》 (最优化方法与软件)

年 卷 期：2001年第15卷第3-4期

页      面：175-200页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：National Science Foundation(CCR-9700448  CCR-9902010  INT-9600343  INT-9910084) 

主　　题：semidefinite programming maxcut approximation algorithm semidefinite relaxation projected gradient method 

摘      要：In this paper, we present a projected gradient algorithm for solving the semidefinite programming (SDP) relaxation of the maximum cut (maxcut) problem. Coupled with a randomized method, this gives a very efficient approximation algorithm for the maxcut problem. We report computational results comparing our method with two earlier successful methods on problems with dimension up to 7,000.