Binary positive semidefinite matrices and associated integer polytopes

• 成果类型: Article
• 署名作者: Letchford, Adam N.; Sorensen, Michael M.
• 署名单位: Lancaster University; Aarhus University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0352-z
• 发表日期: 2012
• 页码: 253-271
• 关键词: clique-web facets; programming relaxations; cut; forms; cone

摘要

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.