5
$\begingroup$

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking for $P$ and $M$ such that the polyhedron $M(P)$ has $\mathcal{O}({c_2}^n)$ vertices, where $c_2$ is a constant.

Are there any other known examples besides 1, 2 (Theorem 4.4)?

$\endgroup$

1 Answer 1

5
$\begingroup$

If I understood your question right, you are looking for a polygon that has a small so-called extended formulation. This problem is studied for example here: http://arxiv.org/abs/1107.0371.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .