Submitted manuscript, 272 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Small bipartite subgraph polytopes
AU - Galli, L
AU - Letchford, A N
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - polyhedral combinatorics
KW - max-cut problem
KW - integrality ratios
U2 - 10.1016/j.orl.2010.05.004
DO - 10.1016/j.orl.2010.05.004
M3 - Journal article
VL - 38
SP - 337
EP - 340
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 5
ER -