Extended formulations for matroid polytopes through randomized protocols |
| |
Institution: | Mathematics Department, Università degli studi di Padova, Via Trieste 63, Padova 35121, Italy |
| |
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. |
| |
Keywords: | Extended formulations Matroids Matroid polytope Randomized protocol Radial cones Spanning tree polytope |
本文献已被 ScienceDirect 等数据库收录! |
|