Home > Research > Publications & Outputs > Small bipartite subgraph polytopes
View graph of relations

Small bipartite subgraph polytopes

Research output: Contribution to journalJournal article


<mark>Journal publication date</mark>2010
<mark>Journal</mark>Operations Research Letters
Issue number5
Number of pages4
Pages (from-to)337-340
<mark>Original language</mark>English


We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.