# Extension complexities of Cartesian products involving a pyramid

@article{Tiwary2017ExtensionCO, title={Extension complexities of Cartesian products involving a pyramid}, author={Hans Raj Tiwary and Stefan Weltge and Rico Zenklusen}, journal={ArXiv}, year={2017}, volume={abs/1702.01959} }

Abstract It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P , Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.

#### Topics from this paper

#### 2 Citations

New limits of treewidth-based tractability in optimization

- Computer Science, Mathematics
- 2018

It is proved that treewidth is the only graph-theoretical parameter that yields tractability for a wide class of optimization problems, a fact well known in Graphical Models in Machine Learning and in Constraint Satisfaction Problems, which here the authors extend to an approximation setting in Optimization. Expand

Limits of Treewidth-based tractability in Optimization

- Mathematics, Computer Science
- ArXiv
- 2018

This work proves that treewidth is the only graph-theoretical parameter that yields tractability in a wide class of optimization problems, a fact well known in Graphical Models in Machine Learning and here it is extended to Optimization. Expand

#### References

SHOWING 1-7 OF 7 REFERENCES

Extension Complexity and Realization Spaces of Hypersimplices

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2018

This work investigates the projective realization spaces of hypersimplices and their (refined) rectangle covering numbers and determines the extension complexity of all hypers Implices as well as of certain classes of combinatorial hypersimplice. Expand

Extended Formulations in Combinatorial Optimization

- Mathematics
- 2011

The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing… Expand

Expressing combinatorial optimization problems by Linear Programs

- Mathematics
- 1991

Abstract Many combinatorial optimization problems call for the optimization of a linear function over a certain polytope. Typically, these polytopes have an exponential number of facets. We explore… Expand

Extended formulations in combinatorial optimization

- Mathematics, Computer Science
- 4OR
- 2010

This survey surveys various tools for deriving and studying extended formulations, such as Fourier's procedure for projection, Minkowski–Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis' theorem on the size of an extended formulation, dynamic programming, and variable discretization. Expand

Sizes of Linear Descriptions in Combinatorial Optimization

- PhD thesis, Otto-von-Guericke-Universität Magdeburg,
- 2016

Integer Programming (Graduate Texts in Mathematics)

- 2014

Integer programming

- Computer Science
- Math. Program.
- 2003

Written by renowned experts in integer programming and combinatorial optimization, Integer Programming is destined to become an essential text in the field. Expand