A projected gradient algorithm for solving the maxcut SDP relaxation

被引：51

作者：

Burer, S

Monteiro, RDC

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

OPTIMIZATION METHODS & SOFTWARE | 2001年 / 15卷 / 3-4期

关键词：

semidefinite programming; maxcut; approximation algorithm; semidefinite relaxation; projected gradient method;

D O I：

10.1080/10556780108805818

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：175 / 200

页数：26

共 23 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].