Binary positive semidefinite matrices and associated integer polytopes

DOI10.1007/s10107-010-0352-zzbMath1235.90113OpenAlexW2135054793WikidataQ57702165 ScholiaQ57702165MaRDI QIDQ662294

Adam N. Letchford, Michael Malmros Sørensen

Publication date: 22 February 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/50252/1/10.pdf

zbMATH Keywords

semidefinite programmingquadratic 0-1 programmingmax-cut problempolyhedral combinatoricsclique partitioning problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

The Boolean Quadric Polytope, Theorems of the alternative for conic integer programming, On Integrality in Semidefinite Programming for Discrete Optimization, Complexity results for the gap inequalities for the max-cut problem, Projection results for the \(k\)-partition problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facets of the clique partitioning polytope
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Facets for the cut cone. I
• The hypermetric cone is polyhedral
• Semidefinite programming in combinatorial optimization
• Stronger linear programming relaxations of max-cut
• On the cone of positive semidefinite matrices
• The cut polytope and the Boolean quadric polytope
• On a positive semidefinite relaxation of the cut polytope
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Clique-Web Facets for Multicut Polytopes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The clique partitioning problem: Facets and patching facets
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• A Note on Clique-Web Facets for Multicut Polytopes
• Discrete and Computational Geometry