A projected gradient algorithm for solving the maxcut SDP relaxation

Samuel Burer; Renato D. C. Monteiro

doi:10.1080/10556780108805818

Back

A projected gradient algorithm for solving the maxcut SDP relaxation

Journal article

Peer reviewed

A projected gradient algorithm for solving the maxcut SDP relaxation

Samuel Burer and Renato D. C. Monteiro

Optimization methods & software, Vol.15(3-4), pp.175-200

01/01/2001

DOI: 10.1080/10556780108805818

View Online

Abstract

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.

Approximation algorithm

Maxcut

Projected gradient method

Semidefinite programming

Semidefinite relaxation

Details

Title: Subtitle: A projected gradient algorithm for solving the maxcut SDP relaxation
Creators: Samuel Burer - Georgia Institute of Technology
Renato D. C. Monteiro - Georgia Institute of Technology
Resource Type: Journal article
Publication Details: Optimization methods & software, Vol.15(3-4), pp.175-200
Publisher: Gordon and Breach Science Publishers
DOI: 10.1080/10556780108805818
ISSN: 1055-6788
eISSN: 1029-4937
Language: English
Date published: 01/01/2001
Academic Unit: Business Analytics
Record Identifier: 9984380513002771

Metrics

1 Record Views

50 Times Cited - Web of Science