A polynomial time algorithm to approximate the mixed volume within a simply exponential factor
| dc.creator | Gurvits, Leonid | |
| dc.date | 2007-02-02 | |
| dc.date | 2009-01-16 | |
| dc.date.accessioned | 2026-07-07T12:31:18Z | |
| dc.date.available | 2026-07-07T12:31:18Z | |
| dc.description | Let ${\bf K} = (K_1, ..., K_n)$ 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 $V_{\bf K}$ is defined as $V_{\bf K}(λ_1, ... ,λ_n) = V(λ_1 K_1 +, ..., + λ_n K_n)$ and the mixed volume $V(K_1, ..., K_n)$ as $$ V(K_1, ..., K_n) = \frac{\partial^n}{\partial λ_1...\partial λ_n} V_{\bf K}(λ_1 K_1 +, ..., + λ_n K_n). $$ Our main result is a poly-time algorithm which approximates $V(K_1, ..., 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, ..., 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. | |
| dc.description | a journal version, accepted to Discrete and Computational Geometry | |
| dc.identifier | https://arxiv.org/abs/cs/0702013 | |
| dc.identifier | http://arxiv.org/abs/cs/0702013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/216401 | |
| dc.subject | Computational Geometry | |
| dc.subject | Computational Complexity | |
| dc.subject | Combinatorics | |
| dc.title | A polynomial time algorithm to approximate the mixed volume within a simply exponential factor | |
| dc.type | text |