Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
From MaRDI portal
Publication:2475315
DOI10.1007/s11425-007-0080-xzbMath1144.90017OpenAlexW1971287361MaRDI QIDQ2475315
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
approximation algorithmmax-cut problemperformance ratiosemidefinite programming relaxationquadratic maximization
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
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
