Regular matroids have polynomial extension complexity

09/18/2019
by   Manuel Aprile, et al.
0

We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n^6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n^2) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset