Department of Economics and Business Economics

Binary Positive Semidefinite Matrices and Associated Integer Polytopes

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

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.
Original languageEnglish
JournalMathematical Programming
Pages (from-to)253-271
Number of pages19
Publication statusPublished - 2012

    Research areas

  • Polyhedral combinatorics, semidefinite programming, max-cut problem, clique partitioning problem, unconstrained boolean quadratic problem

See relations at Aarhus University Citationformats

ID: 231082