We describe a deterministic polynomial-time algorithm
which, for a convex body K in Euclidean n-space, finds upper
and lower bounds on K’s diameter which differ by a
factor of O(p n= log n). We show that this is, within a constant
factor, the best approximation to the diameter that a
polynomial-time algorithm can produce even if randomization
is allowed. We also show that the above results hold for other quantities similar to the diameter - namely, inradius, circumradius, width, and maximization of the norm over K.
In addition to these results for Euclidean spaces, we give
tight results for the error of deterministic polynomial-time
approximations of radii and norm-maxima for convex bodies
in finite-dimensional lp spaces.
«
We describe a deterministic polynomial-time algorithm
which, for a convex body K in Euclidean n-space, finds upper
and lower bounds on K’s diameter which differ by a
factor of O(p n= log n). We show that this is, within a constant
factor, the best approximation to the diameter that a
polynomial-time algorithm can produce even if randomization
is allowed. We also show that the above results hold for other quantities similar to the diameter - namely, inradius, circumradius, width, and maximi...
»