Rounding of polytopes in the real number model of computation

Let A be a set of m points in R(n). We show that the problem of (1 + epsilon)n-rounding of A,, i.e., the problem of computing an ellipsoid E subset of or equal to R(n) such that [(1 + epsilon)n](-1)E subset of or equal to conv. hull(A) subset of or equal to E, can be solved in O(mn(2)(epsilon(-1) + In n + In In m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about A can be solved in O(m(3.5) In(m epsilon(-1))) operations to a relative accuracy of epsilon in the volume. The latter bound also applies to the (1 + epsilon)n-rounding problem. Our bounds hold for the real number model of computation.