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

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

2007-02-02

arxiv.org/abs/cs/0702013v4

Computer Science

Computational Geometry

a journal version, accepted to Discrete and Computational Geometry

Scientific paper

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}}(\lambda_1, ... ,\lambda_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 +, ..., + \lambda_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.

Affiliated with

Also associated with

No associations

Rating

A polynomial time algorithm to approximate the mixed volume within a simply exponential factor does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A polynomial time algorithm to approximate the mixed volume within a simply exponential factor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polynomial time algorithm to approximate the mixed volume within a simply exponential factor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-675924