We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n2) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regularmatroids, for which we give a O(n2) bound.
Regular Matroids Have Polynomial Extension Complexity
Aprile M.;
2022
Abstract
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n2) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regularmatroids, for which we give a O(n2) bound.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Regular matroids.pdf
accesso aperto
Tipologia:
Preprint (submitted version)
Licenza:
Accesso gratuito
Dimensione
359.2 kB
Formato
Adobe PDF
|
359.2 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
