Deterministic and randomized polynomial‐time approximation of radii
DOI10.1112/S0025579300014364zbMATH Open1136.52307OpenAlexW1999351098WikidataQ101069426 ScholiaQ101069426MaRDI QIDQ4435530FDOQ4435530
Miklós Simonovits, László Lovász, Peter Gritzmann, R. Kannan, Andreas Brieden, Victor Klee
Publication date: 16 November 2003
Published in: Mathematika (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/s0025579300014364
Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Computational aspects related to convexity (52B55) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)
Cites Work
- A geometric inequality with applications to linear forms
- Optimization, approximation, and complexity classes
- Title not available (Why is that?)
- 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
- Random walks and anO*(n5) volume algorithm for convex bodies
- Gelfand numbers of operators with values in a Hilbert space
- The law of large numbers and the central limit theorem in Banach spaces
- Approximation of the Sphere by Polytopes having Few Vertices
- A geometric inequality and the complexity of computing volume
- Computational Complexity of Probabilistic Turing Machines
- On the Complexity of Computing the Volume of a Polyhedron
- Lectures on proof verification and approximation algorithms
- Title not available (Why is that?)
- Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
- Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- On the complexity of four polyhedral set containment problems
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Computing the volume is difficult
- Constructing a polytope to approximate a convex body
- Convex Bodies with Few Faces
- Computational complexity of norm-maximization
- On Helly's theorem: Algorithms and extensions
Cited In (17)
- Fixed-parameter complexity and approximability of norm maximization
- Error bounds for consistent reconstruction: random polytopes and coverage processes
- Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
- A note on approximation of a ball by polytopes
- Radii minimal projections of polytopes and constrained optimization of symmetric polynomials
- On the reverse Loomis-Whitney inequality
- Title not available (Why is that?)
- Polytopal approximation of elongated convex bodies
- Geometric clustering for the consolidation of farmland and woodland
- Guarantees for Spontaneous Synchronization on Random Geometric Graphs
- Probability Bounds for Polynomial Functions in Random Variables
- Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints
- 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
- Smallest singular value of random matrices and geometry of random polytopes
- Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
Recommendations
This page was built for publication: Deterministic and randomized polynomial‐time approximation of radii
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4435530)
