Brieden, A.; P. Gritzmann, R. Kannan, V. Klee, L. Lovász and M. Simonovits
Deterministic and randomized polynomial-time approximation of radii
This paper is concerned with convex bodies in n-dimensional lp, spaces, where each body is accessible only by a weak separation or optimization oracle. It studies the asymptotic relative accuracy, as n→∞, of polynomial-time approximation algorithms for the diameter, width, circumradius, and inradius of a body K, and also for the maximum of the norm over K.
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik