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

  • Leonid Gurvits
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , , Short URL: https://optimization-online.org/?p=9031

    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$ .

    Article

    Download

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