Approximation of diameters: Randomization doesn't help

Andreas Brieden, Ravi Kannan, Laszlo Lovasz, Peter Gritzmann, Victor Klee, Miklos Simonovits

Research output: Contribution to journalConference articlepeer-review

20 Scopus citations

Abstract

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(√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.

Original languageEnglish
Pages (from-to)244-251
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1998
EventProceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: 8 Nov 199811 Nov 1998

Fingerprint

Dive into the research topics of 'Approximation of diameters: Randomization doesn't help'. Together they form a unique fingerprint.

Cite this