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.
Galli, L., A. N., L. (2010). Small bipartite subgraph polytopes. OPERATIONS RESEARCH LETTERS, 38(5), 337-340 [10.1016/j.orl.2010.05.004].
Small bipartite subgraph polytopes
GALLI, LAURA;
2010
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.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
