A projected gradient algorithm for solving the maxcut SDP relaxation

DOI10.1080/10556780108805818zbMath1109.90341MaRDI QIDQ2770188

Renato D. C. Monteiro, Samuel Burer

Publication date: 2001

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780108805818

zbMATH Keywords

Semidefinite programming; Approximation algorithm; Semidefinite relaxation; Maxcut; Projected gradient method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C22: Semidefinite programming

90C52: Methods of reduced gradient type

Related Items

Randomized heuristics for the Max-Cut problem, Solving semidefinite programs using preconditioned conjugate gradients, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, Canonical dual approach to solving the maximum cut problem, Semidefinite programming for discrete optimization and matrix completion problems, Solving maximum-entropy sampling problems using factored masks, A discrete filled function algorithm for approximate global solutions of max-cut problems, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, A discrete dynamic convexized method for the max-cut problem, An interior method for nonconvex semidefinite programs, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Drawing (complete) binary tanglegrams, A continuation algorithm for max-cut problem, Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems

Uses Software

• SDPA
• COL

Cites Work

• Unnamed Item
• Semidefinite programming relaxation for nonconvex quadratic programs
• An incomplete Cholesky factorization for dense symmetric positive definite matrices
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Solving Graph Bisection Problems with Semidefinite Programming
• A Spectral Bundle Method for Semidefinite Programming
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• An Interior-Point Method for Semidefinite Programming