  


Binary positive semidefinite matrices and associated integer polytopes
Adam Letchford (a.n.letchfordlancaster.ac.uk) Abstract: 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 maxcut problem, by showing that the rounded psd inequalities define a polytope. Keywords: polyhedral combinatorics, semidefinite programming, maxcut problem Category 1: Integer Programming (01 Programming ) Category 2: Combinatorial Optimization (Polyhedra ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253271. Download: Entry Submitted: 12/16/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  