TY - JOUR

T1 - Binary positive semidefinite matrices and associated integer polytopes

AU - Letchford, A N

AU - Sorensen, M M

N1 - This is the full journal version of a paper that appeared as a chapter in the 2008 IPCO volume.

PY - 2012/2

Y1 - 2012/2

N2 - We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes.We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature—the cut, boolean quadric, multicut and clique partitioning polytopes—are faces of binary psd polytopes. Finally,we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.

AB - We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes.We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature—the cut, boolean quadric, multicut and clique partitioning polytopes—are faces of binary psd polytopes. Finally,we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.

KW - Polyhedral combinatorics

KW - Semidefinite programming

KW - Max-cut problem

KW - Clique partitioning problem

KW - Quadratic 0–1 programming

U2 - 10.1007/s10107-010-0352-z

DO - 10.1007/s10107-010-0352-z

M3 - Journal article

VL - 131

SP - 253

EP - 271

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -