Optimization Online


Small bipartite subgraph polytopes

Laura Galli (l.galli***at***unibo.it)
Adam N. Letchford (A.N.Letchford***at***lancaster.ac.uk)

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
Entry Accepted: 04/22/2010
Entry Last Modified: 02/10/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society