In 1982 Yamnitsky and Levin gave a variant of the
ellipsoid method which uses simplices instead of
ellipsoids. Unlike the ellipsoid method this simplices
method can be implemented in rational arithmetic. We
show, however, that this results in a non-polynomial
method since the storage requirement may grow
exponentially with the size of the input. Nevertheless,
by introducing a rounding procedure we can guarantee
polynomiality for both a central-cut and a shallow-cut
version. Thus in most applications the simplices method
can serve as a substitute for the ellipsoid method. In
particular, it performs better than the ellipsoid
method if it is used to obtain bounds for the volume of
a convex body. Furthermore it can be used to estimate
the optimal function value of total approximation
problems.
