ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 51, 52 Brieden, Andreas, Technische Universität München, Germany Optimal Radii-Algorithms This talk is concerned with convex bodies in n-dimensional l_{p}-spaces that are presented by weak separation oracles. It studies the asymptotic relative accuracy, as n ⟶ ∞, of polynomial-time approximation algorithms for the four main radii of a body K and also for the maximum of the norm over K. The results on order of accuracy are all sharp when p = 2, are sharp for width and inradius when 1 ≤ p ≤ 2, are sharp for diameter, circumradius, and norm-maximization when 2 ≤ p ≤ ∞, and in the remaining cases are within a logarithmic factor of being sharp.