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

DOI10.1007/S00454-009-9147-5zbMATH Open1183.68661arXivcs/0702013OpenAlexW1976658445MaRDI QIDQ1016541FDOQ1016541

Authors: Leonid Gurvits 

Publication date: 6 May 2009

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

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.

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

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

zbMATH Keywords

convex optimizationalgorithmmixed volumeconvex sets

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• 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

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)