The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.
Extended formulations for matroid polytopes through randomized protocols
Aprile M.
2022
Abstract
The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
EXTENDED FORMULATIONS FOR MATROID POLYTOPES.pdf
accesso aperto
Tipologia:
Preprint (submitted version)
Licenza:
Accesso libero
Dimensione
160.46 kB
Formato
Adobe PDF
|
160.46 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
