On The Complexity of Computing Mixed Volumes
\(\# P\)-hardnessapproximationcomputationcomputational complexitycomputational convexityconvex bodydeterminant problemsdeterministic algorithmlattice point enumeratormixed volumesNewton polytopeNP-hardnessparallelotopepartial orderpermanentpolynomial equationspolynomial-time algorithmpolytoperandomized algorithmvolumezonotope
Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Mixed volumes and related topics in convex geometry (52A39) Computational aspects related to convexity (52B55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Convex programming (90C25) Nonlinear programming (90C30)
- scientific article; zbMATH DE number 665697
- scientific article; zbMATH DE number 431987
- On the Complexity of Computing the Volume of a Polyhedron
- Mixed volume computation via linear programming
- A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
- An implementation of exact mixed volume computation
- Unmixing the mixed volume computation
- Computing mixed discriminants, mixed volumes, and permanents
- A geometric inequality and the complexity of computing volume
- scientific article; zbMATH DE number 4112386
- A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
- How to count efficiently all affine roots of a polynomial system
- Toric intersection theory for affine root counting
- The Blaschke-Steinhardt point of a planar convex set
- Some speed-ups and speed limits for real algebraic geometry
- Computing mixed volume and all mixed cells in quermassintegral time
- Sparse resultants and straight-line programs
- Efficiently counting affine roots of mixed trigonometric polynomial systems
- Solving degenerate sparse polynomial systems faster
- Largest \(j\)-simplices in \(n\)-polytopes
- Mixed-volume computation by dynamic lifting applied to polynomial system solving
- Elimination for generic sparse polynomial systems
- Combinatorial mixed valuations
- Unmixing the mixed volume computation
- Computing tropical resultants
- Approximation of convex sets by polytopes
- Volume of convex polytopes equals mixed volume of simplices
- An implementation of exact mixed volume computation
- Heat flow and a faster algorithm to compute the surface area of a convex body
- A practical volume algorithm
- scientific article; zbMATH DE number 431987 (Why is no real title available?)
- A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
- Stochastic Billiards for Sampling from the Boundary of a Convex Set
- On the Complexity of Computing the Volume of a Polyhedron
- scientific article; zbMATH DE number 665697 (Why is no real title available?)
- (Deterministic) algorithms that compute the volume of polytopes
- scientific article; zbMATH DE number 841436 (Why is no real title available?)
- A Polyhedral Method for Solving Sparse Polynomial Systems
- On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data
- Mathematical Foundations of Computer Science 2005
- Approximating the volume of tropical polytopes is difficult
- Extensions of the Kahn-Saks inequality for posets of width two
- A systematic framework for solving geometric constraints analytically
- The convex hull of parking functions of length n
- Counting \(\mathcal{N} = 8\) black holes as algebraic varieties
- Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
- The best ways to slice a polytope
- Estimating Gaussian mixtures using sparse polynomial moment systems
- On the reverse Loomis-Whitney inequality
- On the computation of Newton polytopes of eliminants
- An efficient tree decomposition method for permanents and mixed discriminants
This page was built for publication: On The Complexity of Computing Mixed Volumes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388877)
