Binary positive semidefinite matrices and associated integer polytopes

DOI10.1007/S10107-010-0352-ZMaRDI QIDQ662294zbMATH OpenOpenAlexWikidataFDO

Authors 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

clique partitioning problemmax-cut problempolyhedral combinatoricsquadratic 0-1 programmingsemidefinite programming

Mathematics Subject Classification ID

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

Recommendations

• Positive matrix semigroups with binary diagonals
• Totally positive matrices and cyclic polytopes
• Polytopes of minimum positive semidefinite rank
• Positive semidefinite rank and nested spectrahedra
• A class of positive semidefinite matrices
• Positive Semidefinite Pattern Decompositions
• On permanents of positive semidefinite matrices
• scientific article; zbMATH DE number 70084
• scientific article; zbMATH DE number 1168010

Cites work

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

Cited in

(10)

• Projection results for the \(k\)-partition problem
• Theorems of the alternative for conic integer programming
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• Complexity results for the gap inequalities for the max-cut problem
• The Boolean quadric polytope
• On Integrality in Semidefinite Programming for Discrete Optimization
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization
• New facets of the clique partitioning polytope
• Integer points in arbitrary convex cones: the case of the PSD and SOC cones
• Integer points in arbitrary convex cones: the case of the PSD and SOC cones

This page was built for publication: Binary positive semidefinite matrices and associated integer polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662294)