A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
From MaRDI portal
Publication:6160119
Recommendations
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- Semidefinite programming and integer programming
- A bundle approach for SDPs with exact subgraph constraints
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Algorithmic aspects of using small instance relaxations in parallel branch-and-cut
- All facets of the cut cone \(C_ n\) for \(n=7\) are known
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- An Interior-Point Method for Semidefinite Programming
- Combinatorial optimization and small polytopes
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Cones of Matrices and Set-Functions and 0–1 Optimization
- DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
- Geometry of cuts and metrics
- Handbook on semidefinite, conic and polynomial optimization
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- scientific article; zbMATH DE number 2084783 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Laplacian eigenvalues and the maximum cut problem
- Linear programming relaxations of \textsc{maxcut}
- Local cuts revisited
- On the cut polytope
- On the Shannon capacity of a graph
- Semidefinite programming in combinatorial optimization
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- The expected relative error of the polyhedral approximation of the max- cut problem
- The hypermetric cone is polyhedral
- Upper-bounds for quadratic 0-1 maximization
Cited in
(8)- An SDP-based approach for computing the stability number of a graph
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- On the facets of the lift-and-project relaxations of graph subdivisions
- Partial Lasserre relaxation for sparse Max-Cut
- Strong SDP based bounds on the cutwidth of a graph
- Semidefinite programming and its applications to NP problems
- On different versions of the exact subgraph hierarchy for the stable set problem
- The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
This page was built for publication: A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6160119)
