DocumentCode :
2529918
Title :
Approximation of diameters: randomization doesn´t help
Author :
Brieden, Andreas ; Gritzman, Peter ; Kannan, Ravi ; Klee, Victor ; Lovász, László ; Simonovits, Miklós
Author_Institution :
Tech. Univ. Munchen, Germany
fYear :
1998
fDate :
8-11 Nov 1998
Firstpage :
244
Lastpage :
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(√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 lp spaces
Keywords :
computational geometry; deterministic algorithms; optimisation; polynomial approximation; Euclidean n-space; Euclidean spaces; deterministic polynomial-time algorithm; deterministic polynomial-time approximations; diameters approximation; lower bounds; polynomial-time algorithm; upper bounds; Approximation algorithms; Computer science; Concurrent computing; Cyclic redundancy check; Mathematics; Polynomials; Tellurium;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
ISSN :
0272-5428
Print_ISBN :
0-8186-9172-7
Type :
conf
DOI :
10.1109/SFCS.1998.743451
Filename :
743451
Link To Document :
بازگشت