Günter Rote:

The algebraic conspiracy

In: Oberwolfach Reports, Vol. 14, European Mathematical Society - Publishing House, 2017, pp. 1180–1182. doi:10.4171/OWR/2017/19  →BibTeX


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.

  pdf file
other papers about this subject
Last update: June 5, 2018.