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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.