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 | |
|---|---|---|---|
|
aprile-fiorini-2021-regular-matroids-have-polynomial-extension-complexity.pdf
Accesso riservato
Tipologia:
Published (Publisher's Version of Record)
Licenza:
Accesso privato - non pubblico
Dimensione
889.51 kB
Formato
Adobe PDF
|
889.51 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
Submitted_RegularMatroids.pdf
accesso aperto
Tipologia:
Preprint (AM - Author's Manuscript - submitted)
Licenza:
Accesso libero
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.
