A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor

DOI10.1007/S00454-009-9147-5MaRDI QIDQ1016541zbMATH OpenOpenAlexFDO

Authors Leonid Gurvits

Publication date 6 May 2009

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0702013

zbMATH Keywords

convex optimizationalgorithmmixed volumeconvex sets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation by convex sets (52A27)

Abstract: Let $$ be an $n$-tuple of convex compact subsets in the Euclidean space $R^n$, and let $V(cdot)$ be the Euclidean volume in $R^n$. The Minkowski polynomial $$ is defined as $$ and the mixed volume $V(K_1,\mathrm{...},K_n)$ as ${\displaystyle }$ V(K_1, ..., K_n) = frac{partial^n}{partial lambda_1...partial lambda_n} V_{{�f K}}(lambda_1 K_1 +, ..., + lambda_n K_n). ${\displaystyle }$ Our main result is a poly-time algorithm which approximates $V(K_1,\mathrm{...},K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small. Our approach is based on a particular approximation of $log(V(K_1,\mathrm{...},K_n))$ by a solution of some convex minimization problem. We prove the mixed volume analogues of the Van der Waerden and Schrijver-Valiant conjectures on the permanent. These results, interesting on their own, allow us to justify the abovementioned approximation by a convex minimization, which is solved using the ellipsoid method and a randomized poly-time time algorithm for the approximation of the volume of a convex set.

Recommendations

• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• On The Complexity of Computing Mixed Volumes
• scientific article; zbMATH DE number 665697
• Computing mixed discriminants, mixed volumes, and permanents
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary

Cites work

• scientific article; zbMATH DE number 3704754 (Why is no real title available?)
• scientific article; zbMATH DE number 3790207 (Why is no real title available?)
• scientific article; zbMATH DE number 192855 (Why is no real title available?)
• scientific article; zbMATH DE number 3621721 (Why is no real title available?)
• scientific article; zbMATH DE number 3621932 (Why is no real title available?)
• A Polyhedral Method for Solving Sparse Polynomial Systems
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Algorithm 846
• Computing mixed discriminants, mixed volumes, and permanents
• Computing the volume is difficult
• Counting 1-factors in regular bipartite graphs
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Heat flow and a faster algorithm to compute the surface area of a convex body
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Inequalities between mixed volumes of convex sets
• Mixed discriminants of positive semidefinite matrices
• On The Complexity of Computing Mixed Volumes
• On complexity of matrix scaling
• On the Complexity of Computing the Volume of a Polyhedron
• Polynomial Equations and Convex Polytopes
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• The Van der Waerden conjecture for mixed discriminants
• The solution of van der Waerden's problem for permanents

Cited in

(11)

• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• On The Complexity of Computing Mixed Volumes
• Gauges, loops, and polynomials for partition functions of graphical models
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• Computing mixed volume and all mixed cells in quermassintegral time
• scientific article; zbMATH DE number 841436 (Why is no real title available?)
• Modified log-Sobolev inequalities for strongly log-concave distributions
• Lower bounds for contingency tables via Lorentzian polynomials
• Heat flow and a faster algorithm to compute the surface area of a convex body

Describes a project that uses

Uses Software

• MixedVol

This page was built for publication: A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016541)