Symmetry Matters for the Sizes of Extended Formulations

DOI10.1007/978-3-642-13036-6_11zbMath1285.90052arXiv0911.3712OpenAlexW2111517082MaRDI QIDQ3569814

Dirk Oliver Theis, Kanstantsin Pashkovich, Volker Kaibel

Publication date: 22 June 2010

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Paths and cycles (05C38)

Related Items

Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, The matching problem has no small symmetric SDP, Some \(0/1\) polytopes need exponential size extended formulations, Constructing Extended Formulations from Reflection Relations, Extended formulations in combinatorial optimization, Extended formulations in combinatorial optimization, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Extended formulations, nonnegative factorizations, and randomized communication protocols, Uncapacitated flow-based extended formulations, Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ