Binary Positive Semidefinite Matrices and Associated Integer Polytopes

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • CORAL - Centre for Operations Research Applications in Logistics
  • Erhvervsøkonomisk Institut
  • Institut for Økonomi
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.
OriginalsprogEngelsk
TidsskriftMathematical Programming
Vol/bind131
Nummer1-2
Sider (fra-til)253-271
Antal sider19
ISSN0025-5610
DOI
StatusUdgivet - 2012

Se relationer på Aarhus Universitet Citationsformater

ID: 231082