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 to journalJournal article

Published

Journal publication date02/2012
JournalMathematical Programming
Journal number1-2
Volume131
Number of pages19
Pages253-271
Early online date23/04/10
Original languageEnglish

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 max-cut problem, by showing that the rounded psd inequalities define a polytope.

Bibliographic note

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