Ellipsoidal approximations of convex sets based on the volumetric barrier

The complexity of finding an O(n3/2)-rounding of a convex set C characterized by a separation oracle to O(n2 ln(nR)) oracle calls is reduced. To improve the rounding factor obtained by the volumetric barrier algorithm, or the shallow-cut ellipsoid algorithm, results of Kochol (1994) can be used. By testing O(n) points in the shallow cut oracle used by these algorithms, the rounding factor can be improved to cn (super 3/2).