Home > Research > Publications & Outputs > Small bipartite subgraph polytopes

Electronic data

Links

Text available via DOI:

View graph of relations

Small bipartite subgraph polytopes

Research output: Contribution to journalJournal article

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

Abstract

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.