Small bipartite subgraph polytopes
Laura Galli (l.galliunibo.it)
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.
Keywords: polyhedral combinatorics, max-cut problem
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Integer Programming (0-1 Programming )
Citation: L. Galli & A.N. Letchford (2010) Small bipartite subgraph polytopes. Oper. Res. Lett., 38(5), 337-340.
Entry Submitted: 04/22/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|