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

Leonid Gurvits (gurvitslanl.gov)

Abstract: 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 multiplicative factor $e^n$ .

Keywords: hyperbolic polynomials , permanent , mixed volume , Aleksandrov-Fenchel Inequalities

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation:

Download: [Postscript]

Entry Submitted: 01/19/2006
Entry Accepted: 01/20/2006
Entry Last Modified: 01/22/2006

Modify/Update this entry