A continuation algorithm for max-cut problem

DOI10.1007/S10114-005-0881-1MaRDI QIDQ2644353zbMATH OpenOpenAlexFDO

Authors Feng-Min Xu, Cheng-Xian Xu, Xingsi Li

Publication date 31 August 2007

Published in Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10114-005-0881-1

zbMATH Keywords

augmented Lagrange penalty function methodconvex functionMax-cut problemNCP function

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Nonlinear programming (90C30)

Recommendations

• A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM
• scientific article; zbMATH DE number 5232308
• A multiple penalty function method for solving max-bisection problems
• scientific article; zbMATH DE number 5734227
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

Cites work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A projected gradient algorithm for solving the maxcut SDP relaxation
• A special newton-type optimization method
• A Spectral Bundle Method for Semidefinite Programming
• A tight semidefinite relaxation of the MAX CUT problem
• An improved rounding method and semidefinite programming relaxation for graph partition
• An Interior-Point Method for Semidefinite Programming
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems
• scientific article; zbMATH DE number 2146943 (Why is no real title available?)
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• P-Complete Approximation Problems
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• The non-interior continuation methods for solving the \(P_0\) function nonlinear complementarity problem

Cited in

(13)

• A remark on max-cut problem with an application to digital-analogue convertors
• A gradient-based randomised heuristic for the maximum cut problem
• A discrete dynamic convexized method for the max-cut problem
• A multiple penalty function method for solving max-bisection problems
• Lagrangian smoothing heuristics for Max-cut
• Advanced scatter search for the max-cut problem
• scientific article; zbMATH DE number 5734227 (Why is no real title available?)
• A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM
• scientific article; zbMATH DE number 1786136 (Why is no real title available?)
• Global convergence of the alternating projection method for the max-cut relaxation problem
• scientific article; zbMATH DE number 5232308 (Why is no real title available?)
• An efficient Lagrangian smoothing heuristic for max-cut
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)

Describes a project that uses

Uses Software

• CirCut
• SDPpack
• SDPLR

This page was built for publication: A continuation algorithm for max-cut problem

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