Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

DOI10.1007/s11425-007-0080-xzbMath1144.90017OpenAlexW1971287361MaRDI QIDQ2475315

Da-Chuan Xu, Shu-Zhong Zhang

Publication date: 11 March 2008

Published in: Science in China. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11425-007-0080-x

zbMATH Keywords

approximation algorithmmax-cut problemperformance ratiosemidefinite programming relaxationquadratic maximization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, A novel formulation of the max-cut problem and related algorithm, Robust solutions of uncertain complex-valued quadratically constrained programs, On filter-successive linearization methods for nonlinear semidefinite programming

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating global quadratic optimization with convex quadratic constraints
• Semidefinite programming in combinatorial optimization
• Approximating quadratic programming with bound and quadratic constraints
• Quadratic maximization and semidefinite relaxation
• An improved rounding method and semidefinite programming relaxation for graph partition
• On maximization of quadratic form over intersection of ellipsoids with common center
• Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms
• Outward rotations
• Improved approximation of Max-Cut on graphs of bounded degree
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• New Results on Quadratic Minimization
• Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
• A Spectral Bundle Method for Semidefinite Programming
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• Bipartite Subgraphs and the Smallest Eigenvalue
• On Cones of Nonnegative Quadratic Functions
• Semidefinite programming and combinatorial optimization