On a positive semidefinite relaxation of the cut polytope
From MaRDI portal
Publication:1894508
DOI10.1016/0024-3795(95)00271-RzbMath0835.90078MaRDI QIDQ1894508
Svatopluk Poljak, Monique Laurent
Publication date: 24 July 1995
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Related Items
The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, Disordered systems insights on computational hardness, Intersection bodies of polytopes, Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors, On attainability of Kendall's tau matrices and concordance signatures, On verified numerical computations in convex programming, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, On computational capabilities of Ising machines based on nonlinear oscillators, Some Recent Developments in Spectrahedral Computation, Cuts, matrix completions and graph rigidity, Binary Representation of Normalized Symmetric and Correlation Matrices, Symbolic computation in hyperbolic programming, A Lower Bound on the Positive Semidefinite Rank of Convex Bodies, Efficient rank reduction of correlation matrices, A connection between positive semidefinite and Euclidean distance matrix completion problems, One-third-integrality in the max-cut problem, Parametrising correlation matrices, Generalised 2-circulant inequalities for the max-cut problem, Theorems of the alternative for conic integer programming, A note on the 2-circulant inequalities for the MAX-cut problem, Partial Lasserre relaxation for sparse Max-Cut, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, Gap inequalities for non-convex mixed-integer quadratic programs, The geometry of SDP-exactness in quadratic optimization, Null spaces of correlation matrices, Invariants of SDP exactness in quadratic programming, Complexity results for the gap inequalities for the max-cut problem, Binary positive semidefinite matrices and associated integer polytopes, A guide to conic optimisation and its applications, Valid inequalities for quadratic optimisation with domain constraints, The real positive semidefinite completion problem for series-parallel graphs, Cone-LP's and semidefinite programs: Geometry and a simplex-type method, Iterated linear optimization, Simplicial faces of the set of correlation matrices, Three-by-three correlation matrices: its exact shape and a family of distributions, Exploring the relationship between max-cut and stable set relaxations, Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Asymptotic Bayesian structure learning using graph supports for Gaussian graphical models, COMPATIBILITY AND ATTAINABILITY OF MATRICES OF CORRELATION-BASED MEASURES OF CONCORDANCE, Determinantal sampling designs, Admissible Bernoulli correlations, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP, Binary Component Decomposition Part I: The Positive-Semidefinite Case, An Active-Set Method for Second-Order Conic-Constrained Quadratic Programming, A Semidefinite Hierarchy for Containment of Spectrahedra, A new separation algorithm for the Boolean quadric and cut polytopes, On the separation of split inequalities for non-convex quadratic integer programming, Unnamed Item, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial properties and the complexity of a max-cut approximation
- The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
- Extremal correlation matrices
- Extreme points of a convex subset of the cone of positive semidefinite matrices
- Facets for the cut cone. I
- A note on extreme positive definite matrices
- Geometric algorithms and combinatorial optimization.
- Laplacian eigenvalues and the maximum cut problem
- Node and edge relaxations of the max-cut problem
- On the cone of positive semidefinite matrices
- Cones of diagonally dominant matrices
- The cone of distance matrices
- Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Semi-Definite Matrix Constraints in Optimization
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- A Note on Extreme Correlation Matrices
- On the cut polytope
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- The cut cone. III: On the role of triangle facets
