Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
type: Item
instance of: scholarly article
title: Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
zbMATH Open document ID: 1102.90369
DOI: 10.1016/S0166-218X(01)00266-9
author: Miguel F. Anjos
author: Henry Wolkowicz
published in: Discrete Applied Mathematics
publication date: 2002-06-24T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q99
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 1758388
describes a project that uses: COL
describes a project that uses: SBmethod
describes a project that uses: SDPLIB
describes a project that uses: CSDP
describes a project that uses: SDPpack
MaRDI profile type: Publication
cites work: Strong duality for a trust-region type relaxation of the quadratic assignment problem
cites work: On Lagrangian relaxation of quadratic matrix constraints
cites work: A modified lift-and-project procedure
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: Q3140425
cites work: The max-cut problem on graphs not contractible to \(K_ 5\)
cites work: On cuts and matchings in planar graphs
cites work: An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
cites work: Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
cites work: CSDP, A C library for semidefinite programming
cites work: SDPLIB 1.2, a library of semidefinite programming test problems
cites work: A projected gradient algorithm for solving the maxcut SDP relaxation
cites work: Laplacian eigenvalues and the maximum cut problem
cites work: Geometry of cuts and metrics
cites work: On the optimality of the random hyperplane rounding technique for MAX CUT
cites work: Q4198056
cites work: Semidefinite programming in combinatorial optimization
cites work: Semidefinite programming and combinatorial optimization
cites work: Q4517107
cites work: .878-approximation algorithms for MAX CUT and MAX 2SAT
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Positive definite completions of partial Hermitian matrices
cites work: Q4526964
cites work: Q4517106
cites work: Combining semidefinite and polyhedral relaxations for integer programs
cites work: A Spectral Bundle Method for Semidefinite Programming
cites work: An Interior-Point Method for Semidefinite Programming
cites work: Q4303969
cites work: Q3487569
cites work: An interior-point method for approximate positive semidefinite completions
cites work: Q4142699
cites work: Q4400638
cites work: On a positive semidefinite relaxation of the cut polytope
cites work: On the Facial Structure of the Set of Correlation Matrices
cites work: Connection between semidefinite relaxations of the max-cut and stable set problems
cites work: Q3997942
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Q4281312
cites work: A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
cites work: Q3802887
cites work: Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
cites work: Q5675212
cites work: Nonconvex optimization problem: The infinite-horizon linear-quadratic control problem with quadratic constraints
cites work: Approximating quadratic programming with bound and quadratic constraints
full work available at URL: s0166-218x(01)00266-9
OpenAlex ID: W2136811867
description: scientific article; zbMATH DE number 1758388