We consider the problem of sandwiching a polytope Δ with a given number k of vertices between two nested polytopes P and Q in d dimensions. The polytope P is not necessarily full-dimensional.
Besides the question of (a) computing Δ, we study the following question: (b) Assuming that the given polytopes P and Q are rational polytopes (polytopes with rational vertex coordinates), does it suffice to look for Δ among the rational polytopes?
This problem has several applications: (1) When Q is a dilation of P (or an offset of P), Δ can serve as a thrifty approximation of P. (2) The polytope nesting problem can model the nonnegative rank of a matrix, and thereby the extension complexity of polytopes, as well as other problems in statistics and communication complexity. It was in this context that question (b) was first asked.
Last update: June 5, 2018.