An algebraic approach to symmetric extended formulations
arXiv:1206.6318
Abstract
Extended formulations are an important tool to obtain small (even compact) formulations of polytopes by representing them as projections of higher dimensional ones. It is an important question whether a polytope admits a small extended formulation, i.e., one involving only a polynomial number of inequalities in its dimension. For the case of symmetric extended formulations (i.e., preserving the symmetries of the polytope) Yannakakis established a powerful technique to derive lower bounds and rule out small formulations. We rephrase the technique of Yannakakis in a group-theoretic framework. This provides a different perspective on symmetric extensions and considerably simplifies several lower bound constructions.
arXiv comment21 pages, presented at ISCO 2012
References in corpus (5)
- Symmetry Matters for Sizes of Extended Formulations
- Extended Formulations in Combinatorial Optimization
- Combinatorial Bounds on Nonnegative Rank and Extended Formulations
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results