Deterministic and randomized polynomial‐time approximation of radii

DOI10.1112/S0025579300014364zbMath1136.52307OpenAlexW1999351098WikidataQ101069426 ScholiaQ101069426MaRDI QIDQ4435530

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

Publication date: 16 November 2003

Published in: Mathematika (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/s0025579300014364

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Approximation algorithms (68W25) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Randomized algorithms (68W20)

Related Items

Error bounds for consistent reconstruction: random polytopes and coverage processes, A note on approximation of a ball by polytopes, On the convergence to equilibrium of Kac's random walk on matrices, On clustering bodies: geometry and polyhedral approximation, Constrained clustering via diagrams: a unified theory and its application to electoral district design, Guarantees for Spontaneous Synchronization on Random Geometric Graphs, Polytopal approximation of elongated convex bodies, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints, Geometric clustering for the consolidation of farmland and woodland, Smallest singular value of random matrices and geometry of random polytopes, On the reverse Loomis-Whitney inequality, Radii minimal projections of polytopes and constrained optimization of symmetric polynomials, Probability Bounds for Polynomial Functions in Random Variables, Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems, Fixed-parameter complexity and approximability of norm maximization

Cites Work

• 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
• Random walks and anO*(n5) volume algorithm for convex bodies