= Central-cut ellipsoid volume bound
{title2=$\operatorname{vol}(E')/\operatorname{vol}(E)<e^{-1/(2(n+1))}$}
For $n\geq2$, the standard ellipsoid covering a centrally cut half of the unit ball has center $e_1/(n+1)$ and shape matrix $D'=\frac{n^2}{n^2-1}(I-\frac2{n+1}e_1e_1^T)$. Its eigenvalues are $n^2/(n+1)^2$ along $e_1$ and $n^2/(n^2-1)$ in the other directions. Hence its volume ratio is $R=\frac n{n+1}(\frac{n^2}{n^2-1})^{(n-1)/2}$. Using $\log(1-a)<-a$ and $\log(1+b)<b$ gives $\log R<-1/(2(n+1))$. Affine changes of coordinates preserve the volume ratio. The resulting geometric convergence underlies the <ellipsoid method>; exact rational feasibility additionally needs input-dependent size, precision and lower-dimensional feasibility bounds.
Back to article page
