A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
From MaRDI portal
Publication:6160119
DOI10.3138/infor.53.1.40MaRDI QIDQ6160119
Franz Rendl, Elspeth Adams, Angelika Wiegele, Miguel F. Anjos
Publication date: 9 May 2023
Published in: INFOR: Information Systems and Operational Research (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/85927225/A_Hierarchy_of_Subgraph_Projection_Based_Semidefinite_Relaxations_for_some_NP_Hard_Graph_Optimization_Problems.pdf
Related Items
An SDP-based approach for computing the stability number of a graph, Partial Lasserre relaxation for sparse Max-Cut, Strong SDP based bounds on the cutwidth of a graph, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Handbook on semidefinite, conic and polynomial optimization
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Upper-bounds for quadratic 0-1 maximization
- Local cuts revisited
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- The hypermetric cone is polyhedral
- Laplacian eigenvalues and the maximum cut problem
- Semidefinite programming in combinatorial optimization
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- All facets of the cut cone \(C_ n\) for \(n=7\) are known
- Combinatorial optimization and small polytopes
- The expected relative error of the polyhedral approximation of the max- cut problem
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
- On the cut polytope
- An Interior-Point Method for Semidefinite Programming
- Geometry of cuts and metrics
- Algorithmic aspects of using small instance relaxations in parallel branch-and-cut
