A projected gradient algorithm for solving the maxcut SDP relaxation

DOI10.1080/10556780108805818MaRDI QIDQ2770188zbMATH OpenOpenAlexFDO

Authors Samuel Burer, Renato D. C. Monteiro

Publication date 2001

Published in Optimization Methods \& Software (Search for Journal in Brave)

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

zbMATH Keywords

Approximation algorithmSemidefinite relaxationSemidefinite programmingMaxcutProjected gradient method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Methods of reduced gradient type (90C52)

Recommendations

• scientific article; zbMATH DE number 5060354
• scientific article; zbMATH DE number 5209784
• A novel formulation of the max-cut problem and related algorithm
• A semidefinite programming based polyhedral cut and price approach for the maxcut problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cites work

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

Cited in

(35)

• A semidefinite programming based polyhedral cut and price approach for the maxcut problem
• Solving semidefinite programs using preconditioned conjugate gradients
• A discrete filled function algorithm for approximate global solutions of max-cut problems
• An effective iterated tabu search for the maximum bisection problem
• An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions
• Polyhedral approximations of the semidefinite cone and their application
• Semidefinite programming for discrete optimization and matrix completion problems
• Parameterized algorithms for minimum sum vertex cover
• scientific article; zbMATH DE number 5209784 (Why is no real title available?)
• Canonical dual approach to solving the maximum cut problem
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
• Preemptive and non-preemptive generalized min sum set cover
• Solving maximum-entropy sampling problems using factored masks
• Randomized heuristics for the Max-Cut problem
• A novel formulation of the max-cut problem and related algorithm
• A continuation algorithm for max-cut problem
• Hardness and approximation of submodular minimum linear ordering problems
• An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
• An entropy-regularized ADMM for binary quadratic programming
• A discrete dynamic convexized method for the max-cut problem
• Branch-and-bound algorithms for the K -cluster problem based on SDP bounds evaluated by Lagrangian relaxation
• Drawing (complete) binary tanglegrams
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• scientific article; zbMATH DE number 5060354 (Why is no real title available?)
• An interior method for nonconvex semidefinite programs
• Global convergence of the alternating projection method for the max-cut relaxation problem
• Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems
• A successive quadratic programming algorithm for SDP relaxation of Max-Bisection
• On min sum vertex cover and generalized min sum set cover
• A multiple search operator heuristic for the max-k-cut problem
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
• Parameterized algorithms for minimum sum vertex cover
• Subspace methods for nonlinear optimization
• Block coordinate descent methods for semidefinite programming

Describes a project that uses

Uses Software

• COL
• SDPA

This page was built for publication: A projected gradient algorithm for solving the maxcut SDP relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2770188)