- | ||||
|
![]()
|
Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\
Leonid Gurvits (gurvits 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |