On the extension complexity of combinatorial polytopes

David Avis, Hans Raj Tiwary

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponen…