Symmetry Matters for Sizes of Extended Formulations

DOI10.1137/110839813MaRDI QIDQ4899066zbMATH OpenOpenAlexFDO

Authors Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110839813

zbMATH Keywords

symmetryextended formulationmatching polytopetraveling salesman polytope

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Recommendations

• Uncapacitated flow-based extended formulations
• Extension complexity lower bounds for mixed-integer extended formulations
• A compact linear program for testing optimality of perfect matchings.
• Extended formulations in combinatorial optimization
• Extended formulations for radial cones
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization

Cited in

(14)

• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Lifting for simplicity: concise descriptions of convex sets
• Small extended formulations for cyclic polytopes
• On the combinatorial lower bound for the extension complexity of the spanning tree polytope
• Extension complexity of low-dimensional polytopes
• Hidden vertices in extensions of polytopes
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• Extended formulations for vertex cover
• Pitch, extension complexity, and covering problems
• Symmetry matters for the sizes of extended formulations
• An algebraic approach to symmetric extended formulations
• Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results
• Regular matroids have polynomial extension complexity
• Fooling sets and the spanning tree polytope

This page was built for publication: Symmetry Matters for Sizes of Extended Formulations

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