@inproceedings{,
    author = {Brieden, Andreas; Gritzmann, Peter; Kannan, Ravi; Klee, Victor; Lovász, Laszlo; Simonovits, Miklos},
    title = {Approximation of Diameters: Randomization doesn't help},
    editor = {},
    booktitle = {39th Annual Symposium of the Foundation of Computer Science},
    series = {},
    journal = {},
    address = {Piscataway, NJ},
    publisher = {IEEE Press},
    edition = {},
    year = {1998},
    isbn = {0-8186-9172-7},
    volume = {},
    number =  {},
    pages = {244-251},
    url = {},
    doi = {10.1109/SFCS.1998.743451},
    keywords = {},
    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(/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.},
    note = {},
    institution = {Universität der Bundeswehr München, Fakultät für Wirtschafts- und Organisationswissenschaften, WOW 1 - Institut für Controlling, Finanz- und Risikomanagement, Professur: Brieden, Andreas},
    
    
}