Extended formulations for matroid polytopes through randomized protocols

DOI10.1016/J.ORL.2022.01.011MaRDI QIDQ6371072arXivFDO

Authors Manuel Aprile

Publication date 23 June 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2022.01.011

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

arXiv classification

cs.DMmath.COmath.OC

Abstract: Let $P$ be a polytope. The hitting number of $P$ is the smallest size of a hitting set of the facets of $P$, i.e., a subset of vertices of $P$ such that every facet of $P$ has a vertex in the subset. An extended formulation of $P$ is the description of a polyhedron that linearly projects to $P$. We show that, if $P$ is the base polytope of any matroid, then $P$ admits an extended formulation whose size depends linearly on the hitting number of $P$. Our extended formulations generalize those of the spanning tree polytope given by Martin and Wong. Our proof is simple and short, and it goes through the deep connection between extended formulations and communication protocols.

This page was built for publication: Extended formulations for matroid polytopes through randomized protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6371072)