The relaxation complexity of the standard simplex is logarithmic

Gennadiy Averkov, Simon Keil, Stefan Weltge

For a set $X$ of integer points, the relaxation complexity $\mathrm{rc}(X)$ is the smallest number of facets of any polyhedron $P$ such that $P\cap {\mathbb{Z}}^d=X$. In thi…