Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results

DOI10.1287/moor.2014.0659zbMath1310.90100arXiv0912.3446OpenAlexW2017894167MaRDI QIDQ5247623

Kanstantsin Pashkovich

Publication date: 24 April 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.3446

zbMATH Keywords

extensionsextended formulationspermutahedronsymmetric extensionssymmetric extended formulationscardinality indicating polytopelower bounds on the size of symmetric extended formulations

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items (4)

Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies ⋮ The matching problem has no small symmetric SDP ⋮ Simple extensions of polytopes ⋮ Smallest compact formulation for the permutahedron

Cites Work

• Smallest compact formulation for the permutahedron
• Intermediate integer programming representations using value disjunctions
• Expressing combinatorial optimization problems by linear programs
• Constructing Extended Formulations from Reflection Relations
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Symmetry Matters for Sizes of Extended Formulations
• Extended formulations in combinatorial optimization

This page was built for publication: Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results