Deterministic and randomized polynomial‐time approximation of radii

DOI10.1112/S0025579300014364zbMath1136.52307WikidataQ101069426 ScholiaQ101069426MaRDI QIDQ4435530

László Lovász, Andreas Brieden, Peter Gritzmann, Victor Klee, Miklós Simmonovits, Ravindran Kannan

Publication date: 16 November 2003

Published in: Mathematika (Search for Journal in Brave)

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

52A38: Length, area, volume and convex sets (aspects of convex geometry)

68W25: Approximation algorithms

52A20: Convex sets in (n) dimensions (including convex hypersurfaces)

68W20: Randomized algorithms

Related Items

Radii minimal projections of polytopes and constrained optimization of symmetric polynomials, On clustering bodies: geometry and polyhedral approximation, A note on approximation of a ball by polytopes, On the convergence to equilibrium of Kac's random walk on matrices, Smallest singular value of random matrices and geometry of random polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of norm-maximization
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Random generation of combinatorial structures from a uniform distribution
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• A geometric inequality and the complexity of computing volume
• Computing the volume is difficult
• Gelfand numbers of operators with values in a Hilbert space
• A geometric inequality with applications to linear forms
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Optimization, approximation, and complexity classes
• The law of large numbers and the central limit theorem in Banach spaces
• On the complexity of some basic problems in computational convexity. I. Containment problems
• On Helly's theorem: Algorithms and extensions
• Lectures on proof verification and approximation algorithms
• Constructing a polytope to approximate a convex body
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Convex Bodies with Few Faces
• On the complexity of four polyhedral set containment problems
• On the Complexity of Computing the Volume of a Polyhedron
• Approximation of the Sphere by Polytopes having Few Vertices
• Computational Complexity of Probabilistic Turing Machines