Approximation of Diameters: Randomization Doesn't Help

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(/spl radic/n/logn). 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 l/sub p/ spaces.

Authors

• Andreas Brieden
• Peter Gritzmann
• Ravindran Kannan
• Victor Klee
• László Lovász 0001
• Miklós Simonovits

Keywords

• Polynomials
• Concurrent computing
• Computer science
• Mathematics
• Approximation algorithms
• Tellurium
• Cyclic redundancy check
• Lower Bound
• Hyperplane
• Euclidean Space
• Polynomial Of Degree
• L1-norm
• Degree Of Improvement
• Unit Sphere
• Polynomial-time Algorithm
• Approximate Ratio
• Ball Of Radius
• Polytope
• Minkowski Space
• Space Of Polynomials
• Oracle Model
• Deterministic Approximation
• Circumcircle
• Unit Vector
• Head And Tail