Complexity of polytope volume computation
From MaRDI portal
The author surveys recent complexity results of computing the volume \(V(P)\) of a convex polytope \(P\) in \(\mathbb{R}^ n\). In Part 1 the differentiability properties of \(V(P \cap H(t))\), \(-\infty<t<+\infty\), are investigated where \(H(t)\) is a halfspace of the form \(\{x:x \cdot a \leq t\}\). In Part 2 exact volume computation is discussed and Part 3 contains a description of the randomized algorithm of Dyer, Frieze and Kannan. For the entire collection see [Zbl 0773.00009].
Recommendations
Cited in
(29)- Ehrhart polynomials of matroid polytopes and polymatroids
- Counting linear extensions
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Easy and optimal queries to reduce set uncertainty
- The Santalo point of a planar convex set
- Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space
- The volume of a crosspolytope truncated by a halfspace
- How to integrate a polynomial over a simplex
- A Laplace transform algorithm for the volume of a convex polytope
- Polytope Volume Computation
- scientific article; zbMATH DE number 5302815 (Why is no real title available?)
- Decoupling and Partial Independence
- On the Complexity of Computing the Volume of a Polyhedron
- scientific article; zbMATH DE number 4108152 (Why is no real title available?)
- scientific article; zbMATH DE number 665697 (Why is no real title available?)
- (Deterministic) algorithms that compute the volume of polytopes
- On The Complexity of Computing Mixed Volumes
- Exact volume computation for polytopes: A practical study
- Different Volume Computation Methods of Graph Polytopes
- Performance metric and analytical gain optimality for set-based robust fault detection
- Optimal oversampling ratio in two-step simulation
- A quick estimate for the volume of a polyhedron
- The best ways to slice a polytope
- Partial permutohedra
- The volume of an isocanted cube is a determinant*
- Partial permutohedra
- An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
- Scientific contributions of Leo Khachiyan (a short overview)
- Dispersion of mass and the complexity of randomized geometric algorithms
This page was built for publication: Complexity of polytope volume computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138745)