mixed volume – Optimization Online

Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Published: 2007/02/01, Updated: 2007/04/11

Approximation Algorithms, Convex Optimization convex sets, geometric programming, hyperbolic polynomial, mixed volume

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized 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.\\ Even such rate is impossible to achieve … Read more

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\

Published: 2006/01/19, Updated: 2006/01/22

Leonid Gurvits

Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids aleksandrov-fenchel inequalities, hyperbolic polynomials, mixed volume, permanent

The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more