12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Binary positive semidefinite matrices and assoc...
View graph of relations

« Back

Binary positive semidefinite matrices and associated integer polytopes

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2008
Host publicationInteger Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference
EditorsAndrea Lodi, Alessandro Panconesi, Giovanni Rinaldi
Place of publicationBerlin
PublisherSpringer
Pages125-139
Number of pages15
ISBN (Print)3540688862
Original languageEnglish

Conference

Conference 13th International IPCO Conference
CountryItaly
CityBertinoro
Period26/05/0828/05/08

Publication series

NameLecture Notes in Computer Science
Volume5035

Conference

Conference 13th International IPCO Conference
CountryItaly
CityBertinoro
Period26/05/0828/05/08

Abstract

We consider the positive semidefinite (psd) matrices with binary entries. We give a characterisation of such matrices, along with a graphical representation. We then move on to consider the associated integer polytopes. Several important and well-known integer polytopes (the cut, boolean quadric, multicut and clique partitioning polytopes) are shown to arise as projections of binary psd polytopes. Finally, we present various valid inequalities for binary psd polytopes, and show how they relate to inequalities known for the simpler polytopes mentioned. Along the way, we answer an open question in the literature on the max-cut problem, by showing that the so-called k-gonal inequalities define a polytope.

Bibliographic note

The full version of this paper appeared as: A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253-271.