Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

DOI10.1016/S0166-218X(01)00266-9zbMath1102.90369OpenAlexW2136811867MaRDI QIDQ1602704

Henry Wolkowicz, Miguel F. Anjos

Publication date: 24 June 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00266-9

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Theory of computing (68Q99)

Related Items

On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Mathematical Programming Models and Exact Algorithms, On computational capabilities of Ising machines based on nonlinear oscillators, An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, A continuation algorithm for max-cut problem, Strong duality and minimal representations for cone optimization, Partial Lasserre relaxation for sparse Max-Cut, On Integrality in Semidefinite Programming for Discrete Optimization, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, A semidefinite relaxation based global algorithm for two-level graph partition problem, Ensemble clustering using semidefinite programming with applications, The spherical constraint in Boolean quadratic programs, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Semidefinite programming for discrete optimization and matrix completion problems, Preprocessing and Regularization for Degenerate Semidefinite Programs, An improved semidefinite programming relaxation for the satisfiability problem, Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Computational Approaches to Max-Cut, Solving semidefinite programs using preconditioned conjugate gradients, Spectral bounds for the maximum cut problem, From Graph Orientation to the Unweighted Maximum Cut, Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting, Cuts for mixed 0-1 conic programming, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

Uses Software

• CSDP
• SDPLIB
• SDPpack
• COL
• SBmethod

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• On cuts and matchings in planar graphs
• Positive definite completions of partial Hermitian matrices
• Nonconvex optimization problem: The infinite-horizon linear-quadratic control problem with quadratic constraints
• Laplacian eigenvalues and the maximum cut problem
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A modified lift-and-project procedure
• Semidefinite programming in combinatorial optimization
• Connection between semidefinite relaxations of the max-cut and stable set problems
• An interior-point method for approximate positive semidefinite completions
• Approximating quadratic programming with bound and quadratic constraints
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• On a positive semidefinite relaxation of the cut polytope
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Strong duality for a trust-region type relaxation of the quadratic assignment problem
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On Lagrangian Relaxation of Quadratic Matrix Constraints
• A projected gradient algorithm for solving the maxcut SDP relaxation
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• CSDP, A C library for semidefinite programming
• SDPLIB 1.2, a library of semidefinite programming test problems
• A Spectral Bundle Method for Semidefinite Programming
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• An Interior-Point Method for Semidefinite Programming
• On the Facial Structure of the Set of Correlation Matrices
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Combining semidefinite and polyhedral relaxations for integer programs
• Semidefinite programming and combinatorial optimization
• Semidefinite programming and combinatorial optimization
• Geometry of cuts and metrics