ECCC-Report TR07-037https://eccc.weizmann.ac.il/report/2007/037Comments and Revisions published for TR07-037en-usMon, 23 Apr 2007 00:00:00 +0300
Revision 1
| Polynomial time algorithms to approximate mixed volumes within a simply exponential factor |
Leonid Gurvits
https://eccc.weizmann.ac.il/report/2007/037#revision1Let ${\bf K} = (K_1...K_n)$ be a $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}}(x_1,...,x_n) = V(\lambda_1 K_1 + ... + \lambda_n K_n)$ and the mixed volume $V(K_1,...,K_n)$ as
$$
V(K_1...K_n) = \frac{\partial^n}{\partial \lambda_1...\partial
\lambda_n} V_{{\bf K}}(\lambda_1 K_1 + \cdots
\lambda_n K_n).
$$
In this paper, we study randomized algorithms to approximate the
mixed volume of well-presented convex compact sets. Our main result
is a polynomial time algorithm which approximates $V(K_1,...,K_n)$
with a multiplicative error of $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 convex relaxation of
$\log(V(K_1,...,K_n))$ via geometric programming. We prove the mixed
volume analogues of the Van der Waerden and the Schrijver/Valiant
conjectures for the permanent. These results, though interesting on
their own, allow one to "justify" the above mentioned convex
relaxation. This relaxation is solved with the ellipsoid
method using a randomized polynomial time algorithm for the
approximation of the volume of a convex set.
Mon, 23 Apr 2007 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/037#revision1
Paper TR07-037
| Polynomial time algorithms to approximate mixed volumes within a simply exponential factor |
Leonid Gurvits
https://eccc.weizmann.ac.il/report/2007/037We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.
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 the particular convex relaxation of $\log(V(K_1,...,K_n))$ via the geometric programming.
We prove the mixed volume analogues of
the Van der Waerden and the Schrijver/Valiant conjectures on the permanent. These results , interesting on their own,
allow to "justify" the above mentioned convex relaxation, which is solved using the ellipsoid method and
a randomized poly-time time algorithm for the approximation of the volume of a convex set.
Wed, 18 Apr 2007 04:23:29 +0300https://eccc.weizmann.ac.il/report/2007/037