A geometric inequality and the complexity of computing volume
From MaRDI portal
Publication:1087143
DOI10.1007/BF02187701zbMath0611.52010WikidataQ59410505 ScholiaQ59410505MaRDI QIDQ1087143
Publication date: 1986
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/130996
volumepolynomial time algorithmseparation oraclecomplexity of computing the widthconvex hull of m points in n-dimensional ball
Analysis of algorithms and problem complexity (68Q25) Inequalities and extremum problems involving convexity in convex geometry (52A40)
Related Items (35)
Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies ⋮ On optimal disc covers and a new characterization of the Steiner center ⋮ Approximating the volume of convex bodies ⋮ The curse of dimensionality for numerical integration on general domains ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Computing the volume is difficult ⋮ Concentration phenomena in high dimensional geometry ⋮ On the shape of the convex hull of random points ⋮ Volumes Spanned by Random Points in the Hypercube ⋮ Some more n‐dimensional geometry† ⋮ Blessing of dimensionality at the edge and geometry of few-shot learning ⋮ Some Results on the Complexity of Numerical Integration ⋮ Exploiting sparsity for semi-algebraic set volume computation ⋮ Large deviations, moderate deviations, and the KLS conjecture ⋮ The curse of dimensionality for numerical integration of smooth functions. II ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ (Deterministic) algorithms that compute the volume of polytopes ⋮ Probabilistic Lipschitz analysis of neural networks ⋮ Dispersion of mass and the complexity of randomized geometric algorithms ⋮ Near-optimal deterministic algorithms for volume computation via M-ellipsoids ⋮ Approximating the volume of tropical polytopes is difficult ⋮ Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm ⋮ Uniform generation in spatial constraint databases and applications ⋮ The curse of dimensionality for the class of monotone functions and for the class of convex functions ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Deterministic and randomized polynomial‐time approximation of radii ⋮ How to integrate a polynomial over a simplex ⋮ MCMC convergence diagnosis via multivariate bounds on log-concave densities ⋮ Unnamed Item ⋮ Ehrhart polynomials of matroid polytopes and polymatroids ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises ⋮ Heat flow and a faster algorithm to compute the surface area of a convex body ⋮ On the problem of approximating the number of bases of a matroid ⋮ Similarity of personal preferences: Theoretical foundations and empirical analysis
Cites Work
This page was built for publication: A geometric inequality and the complexity of computing volume
