User: Guest  Login
Title:

Approximation of diameters: randomization doesn’t help

Document type:
Konferenzbeitrag
Contribution type:
Textbeitrag / Aufsatz
Author(s):
Brieden, A.; P. Gritzmann, R. Kannan, V. Klee, L. Lovàsz and M. Simonovits
Pages contribution:
244-251
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(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...     »
Book / Congress title:
1998 IEEE Symp. Found. Computer Sci. (FOCS’98)
Year:
1998
Reviewed:
ja
Language:
en
TUM Institution:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
 BibTeX