Symmetry Matters for Sizes of Extended Formulations
From MaRDI portal
Publication:4899066
DOI10.1137/110839813zbMATH Open1267.90072OpenAlexW1986105362MaRDI QIDQ4899066FDOQ4899066
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
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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
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
- Extension complexity of low-dimensional polytopes
- On the combinatorial lower bound for the extension complexity of the spanning tree polytope
- 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)
